数据结构复习题及参考答案

中南大学网络教育课程考试复习题及参考答案

数据结构

一、填空:

1.设需要对5个不同的记录关键字进行排序，则至少需要比较________次，至多需要比较__________次。 2.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。

3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有_________个。

4.数据结构从逻辑上划分为三种基本类型：___________、__________和___________。

5.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。

6.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。 7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。

8.在快速排序、堆排序、归并排序中，_________排序是稳定的。 9.在有n个叶子结点的哈夫曼树中，总结点数是_______。

10.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定_______。

11.3.已知数组A［10］［10］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［5，6］对应的地址是_______。 12.在有n个结点的无向图中，其边数最多为_______。

13.取出广义表A=(x,(a,b,c,d))中原子x的函数是_______。

14.对矩阵采用压缩存储是为了___ ____。 15.带头结点的双循环链表L为空表的条件是_______。

16.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是 。 17.对于顺序存储的栈，因为栈的空间是有限的，在进行 运算时，可能发生栈的上溢，在进行 运算时，可能发生栈的下溢。

18.在双向链表中，每个结点有两个指针域，一个指向 ，另一个指向 。 19.由一棵二叉树的前序序列和 可唯一确定这棵二叉树。 20.折半查找的存储结构仅限于___ _，且是_ ___。

21.对于一个顺序存储的线性表，在表头插入元素的时间复杂度为____________,在表尾插入元素的时间复杂度为________________。

22.在稀疏距阵所对应的三元组线形表中，每个三元组元素按____________为主序，__________为辅序的次序排列。

23.中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为______________。 24.在一棵高度为h的3叉树中，最多含有_______结点。 25.分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是__ __。

for (i=0;i

26.空串是__ __，其长度等于 。

27.一个图的 表示法是唯一的，而 表示法是不唯一的。

28.在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：

q=head;

while (q->next!=p) q=q->next; s= new Node; s->data=e; q->next= ; //填空 s->next= ; //填空

29.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：

q= p->next;

第1页共22页

p->next= _ ___; //填空 delete ; //填空

30.两个串相等的充分必要条件是____。

31.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是____。

32.二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是____。 33.求下列广义表操作的结果：

(1) GetTail[GetHead[((a,b),(c,d))]];

(2) GetTail[GetHead[GetTail[((a,b),(c,d))]]]

34.已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。 35.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。

36.在利用快速排序方法对一组记录（54，38，96，23，15，72，60，45，83）进行快速排序时，递归调用而使用的栈所能达到的最大深度为____，共需递归调用的次数为____，其中第二次递归调用是对____一组记录进行快速排序。

37.在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取____方法，其次选取____方法，最后选取____方法；若只从排序结果的稳定性考虑，则应选取____方法；若只从平均情况下排序最快考虑，则应选取____方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取____方法。

二、选择题：

1.队列的特点是【 】。

A.先进后出 B.先进先出 C.任意位置进出 D.前面都不正确

2.有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行【 】遍分配与收集。

A.n B.d C.r D.n - d

3.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序【 】。 A.都不相同 B.完全相同

C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同 4.设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为【 】。 A.12 B.13 C.14 D.15 5.下面关于广义表的叙述中，不正确的是【 】。

A.广义表可以是一个多层次的结构 B.广义表至少有一个元素 C.广义表可以被其他广义表所共享 D.广义表可以是一个递归表

6.设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点，下列关系式不正确的是【 】。

k+1k

A.f>=c B.c>f C.f=2-a D.c>s-1 7.从L=((apple,pear),(orange,banana))中，取出banana元素的表达式为【 】。 A.head(tail(L)) B.head(head(tail(L)))

C.tail(head(tail(L))) D.head(tail(head(tail(L)))) 8.下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是【 】。 A.顺序结构 B.链接结构 C.索引结构 D.Hash结构 9.在数据结构中，数据元素可由【 】。

A.实体 B.域 C.数据项 D.字段 10.对于有n个顶点的有向图，由弗洛伊德（FloyD）算法求每一对顶之间的最短路径的时间复杂度是【 】。

3

A.O(1) B.O(n) C.O(n) D.O(n) 11.对n个记录的文件进行快速排序，所需要的辅助存储空间为【 】。

2

A.O(1) B.O(log2 n) C.O(n) D.O(n) 12.哈夫曼树中一定不存在【 】。

A.度为0的结点 B.度为1的结点 C.度为2的结点 D.带权的结点 13.下述哪一条是顺序存储方式的优点？【 】

A.存储密度大 B.插入和删除运算方便

第2页共22页

C.获取符合某种条件的元素方便 D.查找运算速度快

14.有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？（脚注(10)表示用10进制表示，m>3）【 】。 A.658 B.648 C.633 D.653 15.列关于二叉树遍历的叙述中，正确的是【 】。

A.若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B.若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C.若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D.若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 16.层二叉树的结点总数最多为【 】。

kk+1k-1A.2-1 B.2 C.2K-1 D.2 17.线性表进行二分法查找，其前提条件是【 】。 A.线性表以链接方式存储，并且按关键码值排好序

B.线性表以顺序方式存储，并且按关键码值的检索频率排好序 C.线性表以顺序方式存储，并且按关键码值排好序

D.线性表以链接方式存储，并且按关键码值的检索频率排好序 18.n个记录进行堆排序，所需要的辅助存储空间为【 】。

2

A.O(1og2n) B.O(n) C.O(1) D.O(n)

19.线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有【 】个。

A.1 B.2 C.3 D.4 20.列关于数据结构的叙述中，正确的是【 】。 A.数组是不同类型值的集合

B.递归算法的程序结构比迭代算法的程序结构更为精炼 C.树是一种线性结构

D.用一维数组存储一棵完全二叉树是有效的存储方法 21.以下数据结构中哪一个是线性结构？【 】

A.有向图 B.队列 C.线索二叉树 D.B树 22.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下【 】语句序列。

A.p=q; p->next=q B.p->next=q; q->next=p

C.p->next=q->next; p=q; D.q->next=p->next; p->next=q; 23.【 】不是队列的基本运算。

A.在队列第i个元素之后插入一个元素 B.从队头删除一个元素 C.判断一个队列是否为空 D.读取队头元素的值 24.若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为【 】。 A. i B. n=i C. n-i+1 D.不确定 25.栈的特点是【 】，队列的特点是【 】。 A.先进先出 B.先进后出

26.设有两个串p和q，求q在p中首次出现的位置的运算称作【 】。

A.连接 B.模式匹配 C.求子串 D.求串长

27.二维数组A中，每个元素A[i][j]的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为【 】。 A.SA+141 B.SA+180 C.SA+222 D.SA+225

28.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是【 】。

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 29.在一非空二叉树的中序遍历序列中，根结点的右边【 】。

A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点

第3页共22页

30.具有6个顶点的无向图至少应有【 】条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 31.二分查找和二叉排序树的时间性能【 】。 A.相同 B.不相同

32.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为【 】。

2

A.O（n） B.O(nlog2n) C.O(n) D.O(log2n) 33.在待排序的元素序列基本有序的前提下，效率最高的排序方法是【 】。

A.插入排序 B.选择排序 C.快速排序 D.归并排序 34.下述几种排序方法中，要求内存量最大的是【 】。

A.插入排序 B.选择排序 C.快速排序 D.归并排序 35.设有两个串p和q，求q在p中首次出现的位置的运算称作【 】。

A.连接 B.模式匹配 C.求子串 D.求串长

36.二维数组A中，每个元素A[i][j]的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为【 】。 A. SA+141 B. SA+180 C. SA+222 D. SA+225

37.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是【 】。

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 38.在一非空二叉树的中序遍历序列中，根结点的右边【 】。

A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 39.具有6个顶点的无向图至少应有【 】条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 40.二分查找和二叉排序树的时间性能【 】。

A.相同 B.不相同 C.可能相同 D.不确定 41.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为【 】。

2

A.O(n) B.O(nlog2 n) C.O(n) D.O(log2n) 42.在待排序的元素序列基本有序的前提下，效率最高的排序方法是【 】。

A.插入排序 B.选择排序 C.快速排序 D.归并排序 43.下面的序列中【 】是大顶堆。

A.1,2,8,5,3,9,10,4 B.1,5,10,6,7,8,9,2 C.9,8,7,6,4,8,2,1 D.9,8,7,6,5,4,3,1 44.对一个算法的评价，不包括如下【 】方面的内容。

A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度 45.在带有头结点的单链表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 46.对线性表，在下列哪种情况下应当采用链表表示？【 】

A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变

47.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是【 】。 A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 3 48.每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是【 】。 A.冒泡排序 B.简单选择排序 C.希尔排序 D.直接插入排序 49.采用开放定址法处理散列表的冲突时，其平均查找长度【 】。 A.低于链接法处理冲突 B.高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找

50.若需要利用形参直接访问实参时，应将形参变量说明为【 】参数。

A.值 B.函数 C.指针 D.引用

51.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的【 】。 A.行号 B.列号 C.元素值 D.非零元素个数

第4页共22页

52.快速排序在最坏情况下的时间复杂度为【 】。

2

A.O(log2n) B.O(nlog2n) C.O(n) D.O(n) 53.从二叉搜索树中查找一个元素时，其时间复杂度大致为【 】。

2

A.O(n) B.O(1) C.O(log2n) D.O(n)

54.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为【 】。

2

A.O(log2n) B.O(1) C.O(n) D.O(n)

55.设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，??，度数为m的结点数为Nm，则N0=【 】。

A.Nl+N2+??+Nm B.l+N2+2N3+3N4+??+(m-1)Nm C.N2+2N3+3N4+??+(m-1)Nm D.2Nl+3N2+??+(m+1)Nm

56.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为【 】。 A. SA+141 B. SA+144 C. SA+222 D. SA+225

57.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为【 】。 A.uwvts B.vwuts C.wuvts D.wutsv 58.深度为5的二叉树至多有【 】个结点。

A. 16 B. 32 C. 31 D. 10 59.在一个无向图中，所有顶点的度数之和等于所有边数的【 】倍。

A. 1/2 B. 1 C. 2 D. 4

60.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为【 】。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 61.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为【 】。

2

A．O（n） B. O(nlog2n) C. O(n) D. O(log2n) 62.下述几种排序方法中，要求内存量最大的是【 】。

A.插入排序 B.选择排序 C.快速排序 D.归并排序

63.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为【 】。

A.希尔排序 B.起泡排序 C.插入排序 D.选择排序

64.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为【 】的值除以9。

A. 20 B. 18 C. 25 D. 22 65.在有向图中每个顶点的度等于该顶点的【 】。

A.入度 B.出度 C.入度与出度之和 D.入度与出度之差 66.在基于排序码比较的排序算法中，【 】算法的最坏情况下的时间复杂度不高于O(n10g2n)。 A.起泡排序 B.希尔排序 C.归并排序 D.快速排序 67.当α的值较小时，散列存储通常比其他存储方式具有【 】的查找速度。 A.较慢 B.较快 C.相同 D.不清楚

68.设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳【 】个表项。

(设搜索成功的平均搜索长度为Snl＝{1+l／(1一α)}／2，其中α为装填因子) A. 400 B. 526 C. 624 D. 676 69.堆是一个键值序列{k1,k2,?..kn},对I=1,2,?.|_n/2_|,满足【 】 A. ki≤k2i≤k2i+1 B. ki

C. ki≤k2i且ki≤k2i+1(2i+1≤n) D. ki≤k2i 或ki≤k2i+1(2i+1≤n)

70.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上【 】 A.操作的有限集合 B.映象的有限集合 C.类型的有限集合 D.关系的有限集合 71.下列图示的顺序存储结构表示的二叉树是【 】

第5页共22页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构复习题及参考答案在线全文阅读。