数据结构与算法期末测试题.doc

《数据结构与算法期末测试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、宁夏大学期末考试卷2012—2013年第二学期考试科目＿算法与数据结构＿专业＿计算机＿年级＿2011级＿一、选择题1.一个算法的时间复杂度用T(n)表示，其中n的含义是（）A．语句条数B．函数数量C．循环层数D．问题规模2.下列属于线性结构的是（）A．链表B．图C．队列和栈D．广义表3.将长度为m的单链表接在长度为n的单链表之后，其算法的时间复杂度为（）A．O(1)B．O(m)C．O(n)D．O(m+n)4.在头结点的单链表中插入新结点，需要修改的指针数量为（）A．2个B．3个C．4个D．6个5.有一组队列为ABCDE，A为队首元素，①输出首元素。②将首元素插到队尾。③删除首元素④

2、再次删除首元素。重复操作直到空队，则输出的序列为（）A．ACECCB．ACEC．ACECCCD．ACEC6.若栈采用链式存储结构，下列正确的是（）A．需要判断栈满且需要判断栈空B．不需要判断栈满但需要判断栈空C．需要判断栈满但不需要判断栈空D．不需要判断栈满且不需要判断栈空7.设有两个串s和t，求s在t中首次出现的位置的运算称为（）A．连接B．模式匹配C．求子串D．求串长8.串的主要存储表示为（）A．散列表示B．索引表示C．顺序表示D．位表示9.设有一个10阶的下三角矩阵A，采用优先压缩存储方式，a11为第一个元素，其存储地址为1000，一个元素占一个地址单位，则a85的地址为（）

3、A．1012B．1017C．1041D．103910.设深度为k的二叉树只有度为0和度为2的节点，则此类二叉树中包含的节点数至少为（）A．k+1B．2k+1C．2k-1D．2k11.广义表(a,(a,b)d,e.((i,j),k))深度为（）A．6B．5C．4D．312.已知二叉树的后续遍历列式为dabec，中序遍历列式为debac，则前序遍历列式（）A．acbedB．cedbaC．deabcD．decab1.按二叉树定义具有3个结点的二叉树有（）A．5种B．4种C．3种D．6种2.对矩阵压缩存储是为另了（）A．方便运算B．节省空间C．方便存储D．提高运算速度3.下列四个序列中哪个

4、是堆（）A．2，3，10，9，5，7，8，12，11B．12，11，5，2，3，10，9，8，7C．2，3，5，9，10，7，8，12，11D．12，11，7，8，10，9，2，3，5为82的结点时，C次比较后查找成功。4.有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值A．11B．5C．4D．85.一个有n个顶点的无向图中，要连通全部顶点需要（）条边。A．nB．n+1C．n-1D．n/26.散列表的平均查找长度（）A．既与处理方法有关也与表长度有关B．与处理方法无关但是与表长度有关C．与处理方法有关但是与表长度有关D．既与处

5、理方法无关也与表长度无关7.下列排序方法中，（B）是稳定的排序方法A．直接选择排序B．二分法插入排序C．希尔排序D．快速排序8.直接选择排序的时间复杂度为（）（n为元素个数）A．O（n）B．O(log2n)C．O(nlog2n)D．O(n2)二、应用题1.写出下列稀疏矩阵对应的元素组.00101-502030040-20abcedfghi1.一已知二叉树如图所示，写出前序、中序、后序遍历该二叉树所得的三种遍历序列。2.一份电文有5个字符：a，b，c，d，e。所对应的频率分别是：4,7,5,2,9.求对应的哈夫曼树（以左子树的根结点的权小于等于右子树的根结点的权的次序构造）；求每个字

6、符的哈弗曼编码。2543616736558123.使用克鲁丝卡算法造出下面所示G的一棵最小生成树。4.给定一组关键字（46,32,55,81,65,11,25），进行归并排序并写出每趟结果。5.设关键字的输入顺序为：45,24,53,12,28,90，求生成一颗二叉排序树。１32654图G1.一有向图Ｇ如图所示，显示图Ｇ所有拓扑排序序列。三、编程题1.统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex)2.求阶乘的非递归算法。