《数据结构与算法》模拟试卷二.doc

《数据结构与算法》模拟试卷二 一、填空题（每空分，共分） HL=p; p-next=HL; B. p-next=HL; HL=p; C.p-next=HL; p=HL; D.p-next=HL-next; HL-nxet=p; 在一个长度为n的顺序存储的线性表中，删除第i个元素 （1≤i≤n+1）时，需要从前向后依次移动_______个元素。A A.n-i B.n-i+1 C.n-i-1 D.i 在一个顺序队列中，队首指针指向队首元素的_______位置。 A.当前 B.后一个 C.前一个 D.后面 计算递归函数如不用递归过程通常借助的数据结构是____。D A.线性表 B.双向队列 C.树 D.栈 如果T2是由有序树T转换来的二叉树，则T中结点的后序排列是T2结点的____。 A.先序排列 B.中序排列 C.后序排列 D.层序排列 A 栈的插入和删除操作在_____进行。A A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_____。B A. 24 B. 71 C. 48 D. 53 8. 图的广度优先有哪些信誉好的足球投注网站类似于树的_____遍历。D A．先根 B．中根 C. 后根 D．层次9. 在单链表中插入一个结点，要修改_____个结点的指针域。B A. 1 B. 2 C. 3 D. 410.二叉树有_____种基本形态。D A. 2 B. 3 C. 4 D. 5 三、题（要求写出主要步骤及结果。每小题分,共分）’e’,y=’g’; EnQueue(Q,’r’); EnQueue(Q,’d’); EnQueue(Q,y); DeQueue(Q,x); EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,’i’); While(!QueueEmpty(Q)){ DeQueue(Q,y); printf(“%c”,y); } printf(“%c”,x); } 已知如下的一棵二叉树，写出其先序，中序，后序和层序序列。 先序遍历:ABHFDECKG 中序遍历:HBDFAEKCG 后序遍历:HDFBKGCEA 3. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11。试为这8个字母设计哈夫曼编码。并计算其平均编码长度（即WPL）。 4. 使用克里斯卡尔算法构造如下图所示的图G的一棵最小生成树。（画出构造过程） 5. 下图AOE-网表示一个假想的工程，顶点1表示工程开始，顶点9表示工程结束，试求出该AOE-网的关键路径。 6.设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试用快速排序法排序，写出每趟排序后的结果。 7. 设散列表为T[0..12]，散列函数为H(key)=key%13,给定键值序列是{39，36，28，38，44，15，42，12，06，25}，请画出用线性探查法处理冲突时所构成的散列表，并求出在等概率情况下，查找成功的平均查找长度。 四、证明题（要求写出。分）n，则空链域E=n+1,试证明之。 五、算法设计题（共17分1 页 共 3 页】