一．是非题
1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系，P是对D的
基本操作集。
2 简单地说,数据结构是带有结构的数据元素的集合。
3 判断带头结点的非空循环单链表（头指针为L）中指针p所指结点是最后一个元素结点的条
件是：p->next==L。
4线性表的链式存储结构具有可直接存取表中任一元素的优点。
5 线性表的顺序存储结构优于链式存储结构。
6. 在单链表P指针所指结点之后插入S结点的操作是：
P->next= S ; S-> next = P->next;。
7 对于插入、删除而言，线性表的链式存储优于顺序存储。
8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
9.对于插入、删除而言，线性表的链式存储优于顺序存储。
10 线性表的顺序存储结构具有可直接存取表中任一元素的优点。
11. 栈和队列是操作上受限制的线性表。
12. 队列是与线性表完全不同的一种数据结构。
13. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。
14. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。
15. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。
16队列是一种运算受限的线性表
1. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊
情形。
2.二叉树是一棵结点的度最大为二的树。
3. 赫夫曼树中结点个数一定是奇数。
4 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。
5. 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。
6. 通常，二叉树的第i层上有2i-1个结点。
7. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。
8二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。
9二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。
10由树结点的先根序列和后根序列可以唯一地确定一棵树。
1 邻接多重表可以用以表示无向图，也可用以表示有向图。
2 可从任意有向图中得到关于所有顶点的拓扑次序。
3 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。
4. 关键路径是AOE网中源点到汇点的最短路径。
5. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。
6. 一个无向图的连通分量是其极大的连通子图。
7. 连通图的生成树是一个包含图G所有n个顶点和任意n-1条边的子图。
8. 十字链表可以表示无向图，也可用以表示有向图。
9. 邻接表可以表示有向图，也可以表示无向图。（）
1. 二叉排序树的平均查找长度为O(logｎ)。
2. 二叉排序树的最大查找长度与（LOG2N）同阶。
3 选用好的HASH函数可避免冲突。
4折半查找不适用于有序链表的查找。
5一般来说，折半查找不适用于有序链表的查找。
6二叉排序树的查找和折半查找的时间性能相同。
1. 对于目前所知的排序方法，快速排序具有最好的平均性能。
2 对于任何待排序序列来说，快速排序均快于冒泡排序。
3 在最坏情况下，堆排序的时间性能是O(nlogn),比快速排序好
4 快速排序具有最好的平均时间性能，它在任何时候的时间复杂度都是O（n log n）。选择题。
从逻辑上可以把数据结构分成( )。
A. 动态结构和静态结构
B. 顺序组织和链接组织
C. 线性结构和非线性结构
D. 基本类型和组合类型
下列程序段的时间复杂度为( )。
s=i=0;
while (s<=n)
{ i++;
s+=i;
}A. O(1) B. O(n) C. O(n) D. O(n2)
线性表L在( )情况下适于使用链表结构实现。
A. 不需修改L的结构
B. 需不断对L进行删除、插入
C. 需经常修改L中结点值
D. L中含有大量结点
带头结点的单链表L为空的判断条件是。
带头结点的循环链表L为空的判断条件是。
A. L==null
B. L->next==null
C. L->next==L
D. L!=null
若顺序表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定的结点，将该结点与其后继（若存在）结点交换位置，使得经常被查找的结点逐渐移至表尾。以下为据此策略编写的算法，请选择适当的内容，完成此功能。
顺序表的存储结构为：
typedef struct{
ElemType *elem; //数据元素存储空间，0号单元作监视哨
int length; //表长度
}SSTable;
int search_seq(SSTable ST,KeyType key)
{ //在顺序表ST中顺序查找关键字等于key的数据元素。
//若找到，则将该元素与其后继交换位置，并返回其在表中的位置，否则为0。
ST.elem[0].key=key;
i=ST.length;
while(ST.elem[i].key!=key) ;
if( )
{ST.elem[i]←→ST.elem[i+1]；
；
}
return i;
}
A. i>0
B. i>=0
C. i D. i<=ST.length E. i++ F. i-- G. A和C同时满足 H. B和D同时满足 若入栈顺序为A、B、C、D、E，则下列( )出栈序列是不可能的。 A．A、B、C、D、E B．B、C、D、A、E C．C、D、B、E、A D．D、E、C、A、B 递归程序可借助于( )转化为非递归程序。 a.线性表 b.队列 c: 栈 d.数组 在下列数据结构中( )具有先进先出（FIFO）特性， ( )具有先进后出(FILO）特性。 a．线性表 b．栈 c．队列 d．广义表 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 在下列数据结构中( )具有先进先出（FIFO）特性， ( )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 在计算递归函数时，如不用递归过程，应借助于( 2 ) 这种数据结构。 A. 线性表 B. 栈 C. 队列 D. 双向队列 若带头结点的链表只设尾结点指针。下列选择中（）最适用于队列。 A）单链表 B）双向链表 C循环单链表 D）双向循环链表 栈和队列的一个共同点是( )。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 循环队列用数组A[0..m-1]存放其元素值，设头尾指针分别为front和rear，则当前队列中的元素个数是( )。 A. rear-front-1 B. Rear-front+1 C. (rear-front+m)%m D. Rear-front 带头结点的单链表L为空的判断条件是( )。 A. L==null B. L->next==null C. L->next==L D. L!=null 假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7, 19, 22, 6, 32, 14。 若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右），则频率为7的字符编码是（），频率为32的字符编码是（）。 a: 00 b: 01 c: 10 d: 11 e: 011 f: 110 g: 1110 h:1111 对二叉排序树（）可得到有序序列。 ? ? a:按层遍历 b:前序遍历 c:中序遍历 d:后序遍历 设一棵二叉树BT的存储结构如下: 1 2 3 4 5 6 7 8 lchild 2 3 0 0 6 0 0 0 data A B C D E F G H rchild 0 5 4 0 8 7 0 0 其中lchild，rchild分别为结点的左、右孩子指针域，data为结点的数据域。则 该二叉树的高度为( )； 第3层有( )个结点（根结点为第1层）。 A．2 B. 3 C. 4 D. 5 先序遍历图示二叉树可得到（）的序列。 a) A B H D E F I C G b) H B E D F I A C G c)H E I F D B G C A (A) ／＼ (B) (C) ／＼＼ (H) (D) (G) ／＼ (E) (F) ＼ (I) 在有n个结点的二叉树的二叉链表表示中，空指针数（）。 a.不定 b.n+1 c.n d.n-1 若某二叉树有20个叶子结点，有20个结点仅有一个孩子，则该二叉树的总结点数是( )。 A．40 B. 55 C. 59 D. 61 已知某二叉树的先序遍历次序为abcdefg中序遍历次序为badcgfe， 则该二叉树的后序遍历次序为（）。层次遍历次序为（）。 a: abcdefg b: cdebgfa c: bdgfeca d: edcgfba .图示的三棵二叉树中( c)为最优二叉树。 A) B) C) c a 2 7 a b c d d b 7 5 2 4 4 5 a b c d 7 5 2 4 已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG。 则其先序遍历次序为（），层次遍历次序为（）。 a: abcdefg b: abdcefg c: abcdfeg d: abcdegf 已知某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。 若将该树转换为二叉树,其后序遍历次序为（）。 a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba 设x和y是二叉树中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是( )。 A. x是y的左兄弟 B. x是y的右兄弟 C. x是y的祖先 D. x是y的子孙 用三叉链表作二叉树的存储结构，当二叉树中有n个结点时，有( )个空指针。 A. n-1 B. n C. n+1 D. n+2 1. 在有n个结点的二叉树（二叉链表表示）中，空指针数。 A.不定 B.n+1 C.n D.n-1 对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子,其位序是( )。 编号为n的结点若存在双亲,其位置是( )。 a: n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1) 对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子,其位置是( )。 编号为n的结点若存在双亲,其位置是( )。 a: n b: 2n c:2n-1 d:2n+1 e: n /2 f: 2(n+1) 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森林F对应的二叉树根结点的右子树上的结点个数是( 13 )。 A. m1 B. m1+m2 C. m3 D. m2+m3 下列二叉树中，( )可用于实现符号不等长高效编码。 a:最优二叉树 b:次优查找树 c:二叉平衡树 ???d:二叉排序树 邻接表存储结构下图的深度优先遍历算法类似于二叉树的( )遍历。 A. 先根 B. 中根 C. 后根 D. 层次 设无向图G = (V,E)和G’= (V’,E’)，若G’是G的生成树，则下面不正确的说法是( )。 A. G’是G的子图 B. G’是G的连通分量 C. G’是G的无环子图 D. G’是G的极小连通子图且V’= V 任何一个连通图的最小生成树( 27 )。 A．只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 已知某无向图的邻接表如下所示； ( 19 )是其原图。 ( 20 )是按该邻接表遍历所得深度优先生成树。 c d c d c d e f e f e f D. a b E. a b F. a b c d c d c d e f e f e f 深度优先遍历图使用了数据结构（），而广度优先遍历图使用了数据结构（）。 A）数组 B）栈 C）队列 D）线性表 a:弧的数目最多 b:弧的数目最少 c:权值之和最大 d:权值之和最小 1．深度优先遍历图使用了数据结构（），而广度优先遍历图使用了数据结构（）。 A）数组 B）栈 C）队列 D）线性表 已知某有向图的邻接表存储结构如图所示。 根据存储结构依教材中的算法其深度优先遍历次序为（）。 广度优先遍历此序为（）。各强连通分量的顶点集为（）。 a: abcde. b: edcba. c: ecdab. d: ecadb. e: abc及ed f: bc及aed g: ab及ced h: ac及bed 2．下列查找方法中（）适用于查找单链表。 A）顺序查找 B）折半查找 C）分块查找 D）hash查找 c: d: 哈希表的查找效率取决于（）。 a: 哈希函数 b:处理冲突的方法。 c:哈希表的装填因子。 d:以上都是 在Hash函数H(k)=k MOD m中，一般来说，m应取( )。 A. 奇数 B. 偶数 C. 素数 D. 充分大的数 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用方法。 A.设置监视哨 B.链表存贮 C.二分查找 D.快速查找 静态查找表和动态查找表的区别在于( )。 A. 前者是顺序存储，而后者是链式存储 B. 前者只能进行查找操作，而后者可进行查找、插入和删除操作 C. 前者只能顺序查找，而后者只能折半查找 D. 前者可被排序，而后者不能被排序 在一个含有n个元素的有序表上进行折半查找，找到一个元素最多要进行( )次元素比较。 A．?log2(n)? B. ?log2(n)?+1 C. ?log2(n+1)? D. ?log2(n+1)?+1 1．具有m个结点的二叉排序树，其最大深度为（），最小深度为（）。 根据插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序树。 图（）是最终变化的结果。 80 80 70 90 75 90 60 75 85 100 60 70 85 100 72 110 72 110 a: b: 90 90 75 100 80 100 70 80 110 75 70 85 110 60 72 85 60 72 c: d: 若有序表中关键字序列为：14，20，25，32，34，45，57，69，77，83，92。对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是( )。查找32时需进行( )次比较。 A. 1 B. 2 C. 3 D. 4 已知哈希表地址空间为A[0..8]，哈希函数为H(k)=k mod 7，采用线性探测再散列处理冲突。若依次将数据序列：76,45,88,21,94,77,17存入该散列表中，则元素17存储的下标为( )； 在等概率情况下查找成功的平均查找长度为( )。 A. 0 B. 1 C. 2 D. 3 E. 4 F. 5 G. 6 H. 7 若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，则该二叉树是( )。 A. 二叉排序树 B. 赫夫曼树 C. 堆 D. 平衡二叉树 当待排序序列的关键字次序为倒序时，若需为之进行正序排序，下列方案中( 4 )为佳。 A. 起泡排序 B. 快速排序 C. 直接插入排序 D. 简单选择排序 已知一组待排序的记录关键字初始排列如下：56,26,86,35,75,19,77,58,48,42 下列选择中（）是快速排序一趟排序的结果。（）是归并排序 一趟排序的结果。（）是初始堆（大堆顶）。 A）86,75,77,58,42,19,56,35,48,26. B）26,56,35,75,19,77,58,48,42,86. C）35,26,19,42,58,48,56,75,86,77. D）42,26,48,35,19,56,77,58,75,86. 下列排序算法中，( 8 )算法可能会出现：初始数据有序时，花费的时间反而最多。 A. 堆排序 B. 起泡排序 C. 归并排序 D. 快速排序 在下列排序方法中，（）方法平均时间复杂度为0(nlogn)， 最坏情况下时间复杂度为0(n2)；（）方法所有情况下时间复杂度均为0(nlogn)。 a. 插入排序 b. 归并排序 c. 快速排序 d. 堆排序 三．填空题 数据结构通常有下列4类基本结构：集合、、树型结构、图型结构。 设单链表中结点形式为 data next ，若单链表长度大于等于2，指针p指向表中某个结点且 p->next非空，此时若要删除指针p所指的结点，可以通过如下方法进行：将p所指结点的后继 的元素值复制到该结点，然后删除其后继结点。相应的语句序列为： ；；； 线性表的顺序存储结构是以来表示数据元素之间的逻辑关系的。 已知P是单链表中某一结点的指针，P既不是首元结点也不是尾元结点，Q是P 的前驱结点指 针。当删除P结点时，链表的链接可用语句（）实现。 当在P结点之前插入结点S时，链表的链接可用语句（）和语句（）来实现。 注：（不考虑生成或释放结点，仅做链接）。 递归过程可借助于数据结构 ( )改写成非递归过程。 设循环队列存于一维数组Ｑ[ｍ]中，尾指针rear指示队尾元素在队列中的当前位置，?头指针front指示队列中队头元素的前一个位置，则队列长度＝( )。 算法填空 Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)) { //先序非递归遍历二叉树。 Initstack ( S ); Push ( S,T ); While ( !stackempty( S ) ) { While ( gettop( S, p )&& _________________ ) { if (!Visit (p->data ) ) return ERROR; _____________________ ; } Pop ( S , p ); if ( _______________ ) { _______________; push( S, p->rchild ); } } return ok; } 已知某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。 若将该树转换为二叉树,其后序遍历次序为（）。层次遍历次序为（）。 已知某二叉树的先序遍历次序为afbcdeg后序遍历次序为cedbgfa。 其后序遍历次序为（）。层次遍历次序为（）。 在二叉树的第i层上至少有_________个结点, 至多有_________个结点 , 深度为k的二叉树至多有_____________个结点. 对树的遍历有先序遍历树和后序遍历树。若以二叉链表作树的存储结构, 则树的先序遍历可借用二叉树的遍历算法来实现, 而树的后序遍历可借用二叉树的遍历算法来实现。 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少是，至多是。 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3， 则与森林F对应的二叉树根结点的左子树上的结点个数是（）， 右子树上的结点个数是（）。 若某二叉树有n0个叶子结点，有n1个结点仅有一个孩子，则该二叉树的总结点数是（）。对任何一棵二叉树T,若其终端结点数为n0.度为2的结点为n2,则n0与n2的关系为( )。 如果对完全二叉树中结点从1开始按层进行编号，设最大编号为n；那么，可以断定编号为i (i>1) 的结点的父结点编号为( )；所有编号（）的结点为叶子结点。 假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为12，5，7，34，21，11。 若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右），则频率为5的字符编码是（）， 频率为34的字符编码是（）。 若某二叉树中，有20个结点没有孩子，有20个结点仅有一个孩子，则该二叉树的总结点数是。 n个顶点的连通图至少有条边，至多有条边。 对于图的存储结构有（）、（）等方法。 在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是____________条。 若有序表中关键字序列为：12，22，33，44，55，66，77，88，99对其进行折半查找， 则在等概率情况下，查找成功时的平均查找长度是（）。查找99时需进行（）次比较。在哈希表中，处理冲突的方法有开放定址法，， , 。 在二叉树的第i层上至少有_____个结点, 至多有_____个结点 ,深度为k的二叉树至多有个结点. 对于一棵高度为K的二叉排序树，结点数最少可有个，最多可有个。 高度为5二叉排序树，结点数最少有个，最多有个。 用遍历对二叉排序树进行访问可得到有序序列。 已知Hash函数为 H（K）=K mod 13 ，散列地址为0 --14，用二次探测再散列 处理冲突，关键字（23，34，56，24，75，12，49, 52，36，92） 的分布如图，则平均成功的查找长度为（）、平均失败的查找长度为（）。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 在哈希表中，处理冲突的方法有开放定址法，， , 。 哈希表的查找效率取决于（）( )和（）。 对于一棵二叉排序树，通过按( 中序 )次序遍历，可以得到结点的有序序列。 下列算法试图完成在数组A中搜索有无关键字key，若有，返回数组下标,若无，返回-1。在“”处填上合适的内容,完成该算法。 int BinarySearch (keytype A [], int low,int high, keytype key ) { while ( ) { middle = (low+high) /2; if ( ) { return middle; if (key < A[middle]) ; else ; } return -1; } //end of BinarySearch 算法填空 下列函数为堆排序中的堆调整过程（调整H.r[s]的关键字，使H.r[s..m]成为一小顶堆）。 请在“”处填上合适的内容,完成该算法。 Void heapadjust( heaptype @ H , int s , int m ) { rc=H.r[s]; for (j=2*s;j<=m;j*=2) { if (j if ( ) break; H.r[s]=H.r[j]; s=j; } ; }//heapadjust 对n个元素的序列进行内部排序，若用起泡排序法，最少的比较次数是，最多的比 较次数是。 图示结构题 1. 已知在电文中只出现频率为 ( 5,26,7,23,20,19 )的６个字符， 画出你建的哈夫曼树，并给出其哈夫曼编码。 2.已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG 请画出该二叉树，并为之建立先序线索。 3．已知某二叉树的先序遍历次序为：a,b,c,d,e,f,g.中序遍历次序为：b,a,d,f,e,g,c 画出该二叉树，并在该二叉树上建立中序线索。 某二叉树的中序遍历次序为BEGFDAC，先序遍历次序为ABDEFGC。 试画出该二叉树，并为之建立中序线索（图示之）。 1.已知某二叉树的后序遍历和中序遍历次序分别为FBEDGCA和FBADECG，请构造并画出该二叉树。 2.设某一电文只出现a,b,c,d,e,f,g 7个字母；出现频率分别为30%,10%,05%,04%,13%,18%及 20%，请给出各字母的哈夫曼编码。 1．将图示森林转换为二叉树，并对该二叉树先序全序线索化。 1．将图示森林转换为二叉树，并对该二叉树中序全序线索化。 1．某二叉树的结点数据采用顺序存储表示如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 （1）试画出此二叉树的图形表示。 （2）将此二叉树看作森林的二叉树表示，试将它还原为森林。 4.图2所示是某图的邻接表。 ①.请画出该图。 ②.给出一个深度优先序列及其对应深度优先森林(树)。 ??????? ????????? ? 4．设有向图如下，试画出图的邻接表。并给出DFS 及BFS 次序。 4． 已知Hash 函数为 H （K ）=K mod 13 ，散列地址为0 --14，用线性探测再散列处理 冲突，给出关键字（56，34，68，23，16，70，48，35，83，12，14，57） 在散列地址的分布。并指出平均成功的查找长度是多少? 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 设哈希表长为16，哈希函数为H(key)=key mod 13，用开放定址法的二次探测再散列 处理冲突（d i =12，-12，22，-22，32，-32。。。。）。依次存入12个元素：56，82，17,24, 36,21,83,96,13,34,57,50。请画出它们在表中的分布情形。 6． 已知待排序序列为：25,12,9,20,7,31,24,35,17,10，试写出： (1). 堆排序初始建堆(大顶堆)的结果； (2). 以第一个元素为枢轴的快速排序一趟扫描的结果； 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 数据结构例题（及答案） 项目一习题(答案) 一选择题 1. 算法的计算量的大小称为计算的(B )。 A( 效率 B. 复杂性 C. 现实性 D. 难度 2.算法的时间复杂度取决于(C ) A(问题的规模 B. 待处理数据的初态 C. A和B 3(从逻辑上可以把数据结构分为(C )两大类。 A(动态结构、静态结构 B(顺序结构、链式结构 C(线性结构、非线性结构 D(初等结构、构造型结构 4(连续存储设计时，存储单元的地址(A )。 A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续 5. 以下属于逻辑结构的是(C )。 A(顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。(×) 2. 记录是数据处理的最小单位。(×) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×) 4(程序一定是算法。(×) 5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?) 8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×) 三、填空 1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形 结构，图状结构或网状结构四种。 3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而 逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 4(一个数据结构在计算机中表示(又称映像) 称为存储结构。 5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表 示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响 其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互 关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。 ( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、 有一个或多个输8 出。 四、应用题 1. 1. 数据结构是一门研究什么内容的学科, 答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象 及对象间的关系和施加于对象的操作等的学科 2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四 种表示方法 数据结构试题库 一、单项选择题 1．下列程序段所代表的算法的时间复杂度为（D ）。 x=n; y=0; while (x>=(y+1)*(y+1)) y++; (A)O(n) (B)O(n2) (C)O(log2n) (D)O(n) 2．在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置删除元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（B ）。 (A) n2 (B)(n-1)/2 (C)(n+1)/2 (D)n/2 3．在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执行操作为（C ）。 (A)HS->next=s;(B)s->next=HS->next;HS->next=s; (C)s->next=HS;HS=s;(D)s->next=HS;HS=HS>next; 4．假设以带头结点的循环链表表示队列Q，并且队列只设一个头指针front，不设队列尾指针。若要进队一个元素*s，则在下列程序算法的空白处应添加的操作语句是（A ）。 void AddQueue(struct linkqueue Q) { p=Q->front; while(p->next!=Q->front) p=p->next; } (A)p->next=s;s->next=Q->front; (B)Q->front->next=s;Q->front=s; (C)s->next=p;p->next=Q->front; (D)Q->front->next=s;s->next=p; 5．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B ）。 (A)2h-1(B)2h-1+1 (C)2h-1 (D)2h-1-3 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 一、选择题(20分) 1．下面关于线性表的叙述错误的是（D ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 3．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。 (A) 9 (B) 10 (C) 11 (D) 12 4．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（B ）。 (A) O(1) (B) O(log2n) (C) (D) O(n2) 5．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B ）方法可以达到此目的。 (A) 快速排序(B) 堆排序(C) 归并排序(D) 插入排序 第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。 6.下列四种排序中（D ）的空间复杂度最大。 (A) 插入排序(B) 冒泡排序(C) 堆排序(D) 归并排序 7．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 8．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 9．在二叉排序树中插入一个结点的时间复杂度为（B ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2) 10．设用链表作为栈的存储结构则退栈操作（B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．下列四种排序中（A ）的空间复杂度最大。 (A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（C ）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1 (D) N0=2N1+l 13.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过（A ）。 (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1) 14．数据的最小单位是（A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 15．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) 习题1 一、单项选择题 1. 数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5. 算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1）A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2）A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1）A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2）A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8. 数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（）。 A.数据 B.数据元素 C.数据项 D.数据库 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 习题八查找 一、单项选择题 1．顺序查找法适合于存储结构为（）的线性表。 A．散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 3．适用于折半查找的表的存储方式及元素排列要求为( ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5．当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。 A．正确 B. 错误 7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。 A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 10．下图所示的4棵二叉树,( )是平衡二叉树。 （A）（B）（C）（D） 11．散列表的平均查找长度（）。 A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i 第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={数据结构试题及答案(免费)
数据结构经典例题
数据结构试题库
经典数据结构面试题(含答案)
数据结构试题及答案
数据结构试题库答案
大数据结构经典复习题(仅供参考)
数据结构习题及参考答案
数据结构经典例题
数据结构习题及参考答案
数据结构习题及答案
数据结构试题(含答案)
数据结构典型例题
数据结构习题及答案精编版
数据结构经典算法试题
数据结构课后习题及答案
数据结构试题及答案
数据结构课后习题详解(超完整,超经典)
相关主题
文本预览