《武汉大学数据结构考试试题(附答案)》由会员分享，可在线阅读，更多相关《武汉大学数据结构考试试题(附答案)（16页珍藏版）》请在金锄头文库上搜索。
1、武汉大学数据结构考试试题(附答案)1. 下面程序段的执行次数为( A )for (i=0;i Vn-1;i+)for(j二n ;ji;j-)state;A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2)2. 一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第5个元素的地址是( B )A. 110 B .108 C. 100 D. 1203. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是( C )A. edcba B .decba C. dceab D. abcde4. 循环队列用数组A0,m 1 存放其元素值，
2、已知其头尾指针分别是front和rear,则当前队列中的元素个数是(D )A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front5不带头结点的单链表head为空的判定条件是(A ) A.head=NULL B .head-next=NULLC. head-next=head D. head!=NULL6在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行( B)A. s-next=p;p-next=s; B .s-next=p-next;p-next=s;C. s-next=p-next;p=s;
3、D. p-next=s;s-next=p;7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较多少个结点( D )A. n B .n2 C. (n-1)2 D.(n + 1)28从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删 结点的值，则执行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS- next;x=HS-data;D. x=HS-data;HS=HS-next; 9串是一种特殊的线性表， 其特殊性体现在( B )A.可以顺序存储B 数据元素是一个字符C.可以链接存储D.数据 元素可以是多个字符11 二
4、维数组M的元素是4个字符(每个字符占一 个存储单元)组成的串，行下标i的范围从0到4,列下标j的范围从0 到5, M按行存储时元素M的起始地址与M按列存储时下列哪一元素的起始地址相同( B ) A. M B .M C. M D. M12. 数组A中，每个元素A的长度为3个字节，行下标i从1到8, 列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行 存放时，元素A的起始地址为(C )A. SA+144 B .SA+180 C. SA+222 D. SA+22513. 设髙度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：( B )A. 2h B .2h
5、-1 C. 2h+1 D. h+114. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是(D )A. acbed B .decab C. deabc D. cedba15. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍 历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化 得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确( A )A. 树的先 根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对 16. 具有
6、 6 个顶点的无向图至少应有多少条边才能确 保是一个连通图( A )A. 5 B .6 C. 7 D. 817. 顺序查找法适合于存储结构为( B )的线性表 A. 散列存储 B .顺序 存储或链接存储 C. 压缩存储 D. 索引存储18.采用顺序查找方法查找长度为 n 的线性表每个元素的平均查找长 度为( C )A. n B .n2 C. (n+1)2 D. (n-1)219. 有一个长度为 12 的有序表，按二分查找法对该表进行查找，在 表内各元素等概率情况下查找成功所需的平均比较次数为( B )A. 3512 B .3712 C. 3912 D. 431220.有一个有序表为1，3，9，
7、12，32，41，45，62，75，77，82， 95，100，当二分查找值 82为的结点时，几次比较后查找成功( C )二、填空题(每空 1分，共 20分)1. 在线性表的顺序存储中，元素之间的逻辑关系是通过物理存储位 置，决定的；在线性表的链接存储中，元素之间的逻辑关系是通过链域的 指针值决定的。2对于一个具有N个结点的单链表，在已知的结点P后 插入一个新结点的时间复杂度为0(1)，在给定值为X的结点后插入一个新 结点的时间复杂度为0(N)。3有一空C,现有输入序列12345，经 push,push,pop,push,pop,push,push 后，输出序列为 2,3 。4在一个无向图中，
8、所有顶点的度数之和等于所有边数的 2 倍 5. 对于一棵具有 n 个结点的树，该树中所有结点的度数之和为 n-1。6. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为 1 的结点数为 2 个，那么度为 0 的结点数有 6 个7.在霍夫曼编码中，若编码长度只允许小于等于 4，则除了已对两个 字符编码为 0 和 10 外，还可以最多对 4 个字符编码。8. 对于一个具有 n 个顶点和 e 条边的连通图，其生成树中的顶点数 和边数分别为 n 和 n-1 。9. 对 20 个记录进行归并排序时，共需要进行 5 趟归并，在第三趟 归并时是把长度为 4 的有序表两两归并为长度为 8 的有
9、序表。三、问答题 1. 简述下面算法的功能(栈和队列的元素类型均为 int) void algo3(Queue Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q)DeQueue(Q,d);Push(S,d);while(!StackEmpty(S)Pop(S,d); EnQueue(Q,d);算法的功能：利用栈作辅助，将队列中的数据元素进行逆置2. 已知一棵二叉树的中序遍历序列和先序遍历序列为，试问能不能 唯一确定一棵二叉树。若给定先序遍历序列和后序遍历序列，能不能唯一 确定呢？由中序遍历序列和先序遍历序列能唯一确定一棵二叉树。由先序遍历 和后
10、序遍历序列不能唯一确定一棵二叉树.。一、选择题1. 下面程序段的执行次数为( )for (i=0;i Vn-1;i+)for(j二n ;ji;j-)state;A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2)2. 判定一个栈ST (最多元素为m0)为空的条件是：()A. ST-topO B .ST-top = 0C. ST-topmO D. ST-top = m03. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是()A. edcba B .decba C. dceab D. abcde4. 在一个单链表中，若p所指的结点不是
11、最后结点，在p之后插入s 所指结点，则执行( ) A. s-next=p;p-next=s;B .s-next=p-next;p- next=s;C. s-next=p-next;p=s;D. p-next=s;s-next=p; 5 在一个链队中， 假设f和r分别为队首和队尾指针，则删除一个结点的运算时()A. r=f- next; B .r二r-next; C. f=f-next;D. f二r-next;6 串是一种特殊的线性表，其特 殊性体现在( ) A. 可以顺序存储 B .数据元素是一个字符 C. 可以链接 存储 D. 数据元素可以是多个字符7. 稀疏矩阵一般的压缩方法有两种， 即(
12、 ) A. 二维数组和三维数组 B .三元组和散列 C. 三元组和十字链表 D. 散列和十字链表 8 将递归算法转换成对应的非递归算法时，通常需要 使用()A.栈B 队列C.链表D.树9二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4,列下 标j的范围从0到5，M按行存储时元素M的起始地址与M按列存储时 下列哪一元素的起始地址相同()A. M B .M C. M D. M10.数组A中，每个 元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首 地址 SA 开始连续存放在存储器内，该数组按行存放时，元素A的起始地址为()A.SA+144 B .
13、SA+180 C. SA+222 D. SA+_.如果T2是由有序树T转换而来 的二叉树，那么T中结点的后序就是T2中结点的()A.前序B冲序C. 后序 D. 层次序12.一个有n个顶点的无向图最多有多少边()A. n B .n(n-1) C. n(n-1)2 D. 2n13. 按照二叉树的定义，具有 3个结点的二叉树有( )种 A. 3 B .4 C. 5 D. 6 14.在一非空二叉树的中序遍历序列中，根结点的右边( )A. 只有右子 树上的所有结点 B .只有右子树上的部分结点 C. 只有左子树上的部分结 点 D. 只有左子树上的所有结点15. 在一个图中，所有顶点的度数之和等于所有边数
14、的多少倍( )A. 12B .1 C. 2 D. 416. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )A. 先 序遍历 B .中序遍历 C. 后序遍历 D. 按层遍历17. 采用顺序查找方法查找长度为 n 的线性表每个元素的平均查找长 度为( )A. n B .n2 C. (n+1)2 D. (n-1)2二、填空题 1. 算法的计算量的大小称为计算的_ _。 2数据结构 是研究数据的 和 以及他们之间的相互关系，并对这种结构定义相应的运算,设计出相应的 ,而确保经过这些运算后所得的 新结构是 结构类型。3在一个单链表中删除 p 结点，应执行下列操作：q=p-next;p-data
15、=p-next-data;p-next= ;free（q）;4有一空C,现有输入序列54321,经 push,push,pop,push,pop,push,push 后，输出序列为 。5在双向链表中每个结点包含两个指针域,一个指向 结点,另一个 指向 结点。 6一维数组的逻辑结构是 ,存储结构是 。 7.对于一棵含有 40 个结点的理想平衡树,它的高度为 。8假定对长度n = 50的有序表进行折半搜索，则对应的判定树髙度为 , 判定树中前 5 层的结点数为 , 最后一层的结点数为 。 9. 假定一组记 录的排序码为（46， 79， 56， 38， 40， 80），对其进行归并排序的过程 中，第二趟归并后的结果为 。10. 假定一组记录的排序码为（46，79， 56， 38， 40， 80），对其进行快速排序的一次划分的结果为。三、简答题1假定有四个元素A,B,C,D依次进栈，进栈过程中允许出 栈，试写出所有可能的出栈序列？ 2.棵含有n个结点的k叉树，可能达 到的最大深度和最小深度各为多少？ 3. 设有 5000 个无序的元素，希望 用最快速度挑选出其中前 10 个最大的元素，在以下的排序方法中，采用 哪种方法最好？为什么？(快速排序，堆排序，基数排序)一、选择题 1. B 2. B 3. C 4. B 5C 6B 9C
