《数据结构期末考试试题.doc》由会员分享，可在线阅读，更多相关《数据结构期末考试试题.doc（6页珍藏版）》请在三一文库上搜索。
1、1线性链表不具有的特点是（ ）。A随机访问 B不必事先估计所需存储空间大小C插入与删除时不必移动元素 D所需空间与线性表长度成正比2设一个栈的输入序列为1，2，3，4，则输出序列不可能是( )。A1, 2, 3, 4 B4, 3, 2, 1 C1, 3, 2, 4 D4,1,2,33下列排序算法中，( )排序在每趟结束后不一定能选出一个元素放到其排好序的最终位置上。 A归并 B冒泡 C选择 D堆4下列序列中，( )是执行第一趟快速排序后得到的序列(排序的关键字类型是字符串)。Ada, ax, eb, de, bb ff ha, gc Bcd, eb, ax, da ff ha, gc, bbC
2、gc, ax, eb, cd, bb ff da, ha Dax, bb, cd, da ff eb, gc, ha5设有一个10阶的对称矩阵A1010，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B 中，A00存入B0中，则A85在B 中（ ）位置。A32 B33 C41 D656. 下面哪一种图的邻接矩阵肯定是对称矩阵( )。A有向图 B无向图 CAOV网 DAOE网7具有2008个结点的二叉树，其深度至少为( )。A9 B10 C11 D128. 关键路径是边表示活动的网（AOE网）中的( )。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长的回路D最短的回路9 一个
3、广义表为(a, (a,b), d, e, (i,j) ,k)，则该广义表的长度为( )。A不确定 B8 C5 D610设循环队列中数组的下标范围是0n 1，其头尾指针分别为f和r，则其元素个数为( )。Ar f Br f + 1 C( r f ) mod n + 1 D( r f + n ) mod n1算法具有的五个重要特性是：有穷性，确定性，_，输入和输出。2一组记录的关键字为（45,80,55,40,42,85），则利用堆排序的方法建立的初始堆为_。3对如下无向图G，从结点V1出发，写出一个按深度优先遍历图的结点序列：_。V1 V6V2 V8V7V4V3 V5 第3题图 第4题图4写出右
4、上图中的一个拓扑有序序列_。 5对于顺序存储的线性表，访问结点和删除结点的时间复杂度分别为_。6平衡二叉树上所有结点的平衡因子只可能是_。7假定对线性表R1.60进行分块查找，共分为10块，每块长度等于6。若假定查找索引表和块均用顺序查找的方法，则查找每一个元素的平均查找长度为_。8将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为37的双亲结点编号为_。 9设有一个字符串 s=science，其非空子串的数目是_。10有n个顶点的强连通有向图G至少有_条弧。1 一棵二叉树的先序序列和中序序列分别如下， 先序序列： ABCDEFGHI
5、J 中序序列： CBDEAGIHJF（1） 画出该二叉树。（3分）（2） 写出其后序序列。（3分）2给出用Kruskal算法构造下列带权图的最小生成树的过程。V1V2 3 V3 1 5 4V6 3 V4 4 1 6V5 23. 已知一个长度为12的表（6，8，4，12，2，10，7，3，9，1，11，5）。（1）将表中的元素依次插入到一个初始为空的二叉排序树中，画出该二叉排序树并求其在等概率下的平均查找长度。（3分）（2）若先对表中的记录排序，构成有序表后再对其进行折半查找，画出判定树并求其在等概率下的平均查找长度。（3分）4已知哈希表地址空间为0.10，哈希函数为H(key) = key M
6、OD 11，采用链地址法处理冲突，将下面数据序列依次插入该哈希表中，并求出在等概率下查找成功时的平均查找长度。12，24，1，34，38，44，27，22。5假定用于通信的电文仅由8个字母a，b，c，d，e，d，f，g，h组成，各个字母在电文中出现的频率分别为5，23，3，6，10，11，36，4。要求：（1）以这些频率作为叶子结点的权值构造Huffman树。（2分）（2）试为这8个字母设计不等长Huffman编码。（2分） A b c d e f g h（3）计算出电文总长度。（2分）1. 有两个不带头结点的单循环链表，链表头指针分别为a和b。编写一个过程将链表b链到链表a之后，链接后的链表
7、仍保持循环链表形式。2. 试编写一个计算二叉树的叶子结点数的算法。要求二叉树采用链式存储结构。3. 请写出监视哨设在高下标端的插入排序算法。06 21. 具有n(n0)个结点的完全二叉树的深度为 （ ）A. log2n B. log2n C. log2n +1 D. log2n+12. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 （ ）A.abcde B.edcbaC.decba D.dceab3. 数据在计算机存储器内表示时，物理地址与逻辑地址相同且连续，称之为 （ ）A.存储结构 B. 逻辑结构 C.顺序存储结构 D. 链式存储结构4. 对二叉排序树的左子树中所有结点与
8、右子树中所有结点的关键字大小关系是 ( )A.小于 B.大于 C.等于 D.不小于5. 按照二叉树的定义，具有3个节点的二叉树_种 （ ）A.2 B.3 C.4 D. 56. 广义表（a）的表尾是 ( )Aa B. （a） C（） D. (（a）)7设有两个串p和q，求在q在p中首次出现的位置的运算称为 （ ）A.模式匹配 B.连接 C.求子串 D. 求串长8. 引入二叉线索树的目的是 （ ）A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一9在有n个叶子结点的哈夫曼树中，其结点总数为 A.不确定 B.2n-1 C.2n D.
9、2n+110与单链表相比，双向链表的优点之一是 A插入、删除更简单 B.可以进行随机访问C可以省略表头指针或表尾指针 D.访问前后相邻结点更方便1Prim算法适合求_的网的最小生成树，而Kruskal算法适用于求_的网的最小生成树。 2.循环单链表L为空的条件是_。 3.在对队列中，新插入的元素只能插入到_。 4平衡二叉树上所有结点的平衡因子只可能是_。5一个有序表1，3，9，12，32，41，45，62，75，77，82，95，99，当采用折半查找法查找关键字为82的元素时，_次比较后查找成功。6设二维数组A610,每个数组元素占4个存储单元，若按行优先顺序存放数组元素，A00的存储地址是8
10、60，则A35的存储地址是_。7可以进行拓扑排序的一定是_。8求单链表长度算法的时间复杂度是_。9.在直接插入排序、希尔排序、直接选择排序、快速排序、堆排序和归并排序中，平均比较次数最少的排序方法是_。1.已知一个二叉树的中序遍历序列为DGBAECF, 后序遍历序列为GDBEFCA, 请给出：（3） 画出该二叉树。（3分）（4） 写出其后序序列。（3分）对关键字序列11,78,10,1,3,2,4,21构造哈希表，取散列地址为HT0.10，散列函数为H(K)K11，试用线性探查法冲突，画出相应的哈希表，并分别求查找成功和不成功时的平均查找长度。3. 已知关键字序列503，87，512，61，9
11、08，170，897，275，653，462，采用快速排序算法对该序列作升序排序时的每一趟的结果。4. 从一棵空树开始，逐个读入并插入下列关键字： 40，28，6，72，100，3，54，1，80，91，38请首先建立二叉排序树，然后删除节点72，并给出删除节点72后的二叉树。5. 给定权集W=2,3,4,7,8,9,试构造关于W的一棵哈夫曼树，并求带权路径长度WPL。1. 有一个有序单链表（从小到大排序），表头指针为L，设计一个算法向该单链表中插入一个元素为x的结点，并使插入后链表仍然有序。2. 二叉树采用链式存储结构，试编写算法求二叉树的深度。3. .二叉树采用链式存储结构，试设计一个按层
12、次顺序（同层自左向右）遍历二叉树的算法。答案A一、 选择题（每小题2分，共20分）1.A2.D 3.A 4.A 5.C 6.B 7.C 8.A 9.C 10.D二、填空题（每小题2分，共20分）1可行性 2（85,80,55,40,42,45） 3V1, V2, V3, V5 ,V4,V6, V7, V8 (答案不惟一)41, 2, 3, 5, 6, 4 (答案不惟一) 5. O(1)和 O( n) 6. 1, 0, 1 7. 9 8. 18 9. 26 10n三、解答下列各题 (每小题6分，共30分)1该二叉树为（3分）： A B F C D G E H I J后序序列：CEDBIJHGFA
13、 （3分）2 V1 V2 V1 V2 V1 V2 1 1 1 V3 V6 V3 V6 V3 V6 1 1 V4 V5 V5 V4 2 V5 （2分） （1分） （1分） V1 3 V2 V1 3 V2 1 1 4 V3 V6 V3 V6 1 1 V4 2 V5 V4 2 V5 （1分） （1分）3（1）二叉排序树为： 6 4 8 2 5 7 12 1 3 10 9 11 （ 2分）等概率下平均查找长度 ASL =（1+2*2+3*4+4*3+5*2）/12 = 13/4 = 3.25 （1分 ）（2）排序后进行折半查找的判定树为： 6 3 9 1 4 7 11 2 5 8 10 12 （2分）
14、等概率下平均查找长度 ASL =（1+2*2+3*4+4*5）/12 = 37/12 3.08 （1分）第1页(共3页)4哈希函数值为：（1分） H(12)=1 H(24)=2 H(1)=1 H(34)=1 H(38)=5 H(44)=0 H(27)=5 H(22)=0 哈希表为：（3分） 0 22 44 1 1 12 34 2 24 3 4 5 27 38 6 7 8 9 10 平均查找长度 ASL = (14+23+31)/8 = 13/8=1.625 （2分）5（1）Huffman树为：（2分） 98 39 59 17 22 23 36 7 10 11 11 3 4 5 6 （2） 其h
15、uffman编码为 （2分）注：此题答案不唯一，只要满足哈夫曼编码的要求都可。abcdEfgH01001000000101001011110001（3）电文总码数为4*5+2*23+4*3+4*6+3*10+3*11+2*36+4*4=253 （2分）四、算法设计(每小题10分，共30分 )说明：每小题中：1思路正确3分2算法正确5分3算法完整2分（1）typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;void Connect( LinkList a, LinkList b ) /将循环链表b链在循环链
16、表a之后的算法，链表a和b均不带头结点LinkList p;p=a; /先令指针p指向链表a的第一个结点while(p-nexta)p = p-next; /找到链表a的最后一个结点p-next=b; /将链表b链到a的最后一个结点之后第2页(共3页)p=b; /令指针p指向链表b的第一个结点while(p-nextb)p = p-next; /找到链表b的最后一个结点p-next=a; /令链表b的最后一个结点指向合并后的链表的表头（2）Typedef struct BiTNodeTelemType data;Struct BiTNode *lchild, *rchild;BiTNode,
17、*BiTree;void leaf(BiTree T) /采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点/的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的个数/第一 次被调用时，n=0if(T) /若二叉树为空，结束返回 /若二叉树不为空，在先序遍历二叉树的过程中，统计叶子结点的个数 if(T-lchild=null&T-rchild=null) n=n+1; leaf(T-lchild); leaf(T-rchild); /if/leaf（3）typedef struct KeyType key; InfoType otherinfo;RedType;typedef s
18、truct RedType rMAXSIZE+1; int length;SqList;void Insert_Sort1(SqList &L)/监视哨设在高下标端的插入排序算法 k=L.length; for(i=k-1;i;-i) /从后向前逐个插入排序if(L.ri.keyL.ri+1.key)L.rk+1.key=L.ri.key; /监视哨for(j=i+1;L.rk+1.keyL.rj.key;+j)L.rj-1=L.rj; /前移L.rj-1=L.rk+1; /插入/Insert_Sort1 B一、 选择题（每小题1分，共10分）1-5 C D C B D 6-10 C A A
19、D D 二、 填空题（每空2分，共20分）1. 边稠密，边稀疏2. L-next=L;3. 队尾4. -1，0，15. 46. 10007. 无环图8. O(n)9. 快速排序三、解答题（每小题6分，共30分）1. （1）二叉树是： （4分）（2）后序序列为：GDBEFCA （2分）2. 解：首先求出散列地址，据此得到哈希表见下图。0 1 2 3 4 5 6 7 8 9 10117813242110查找成功的平均比较次数为：ASL(1121328l)82.375查找不成功的平均查找长度为：ASLunsucc(87654321119)114.2733.每趟快速排序的结果如下：462 87 275
20、 61 170 503 897 908 653 512170 87 275 61 46261 87 170 27561 87 512 653 897 908 512 653排序后：61 87 170 275 462 503 512 653 897 908 4. 二叉排序树： （4分）删除72后： （2分）5. 构造的哈夫曼树为：（4分）加权路径长度WPL=80 （2分）四、算法设计题（每小题10分，共30分）1. void ListInsert(Linklist &L,int x) Linklist *p,*q; q=L; p=q-next; while(p&xp-data) q=p; p=p
21、-next; s=(Linklist)malloc(sizeof(LNode);s-data=x;s-next=p;q-next=s;2.int BtDepth（Bitree T） int lchilddep,rchilddep;if(T) return(0);else lchilddep= BtDepth（T- lchild）;rchilddep= BtDepth（T- rchild）; return(lchilddep rchilddep)? (lchilddep+1): (rchilddep+1); 3.void LayerOrder(Bitree T) InitQueue(Q); EnQueue(Q,T); while( !QueueEmpty(Q) ) DeQueue(Q, &p); visit(p); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild);