发布时间 : 星期五 文章数据结构复习题及参考答案更新完毕开始阅读07758f7bc850ad02df804100
中南大学网络教育课程考试复习题及参考答案
数据结构
一、填空:
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页