《算法与数据结构》A卷

1、2011-2012（A）课程名称 算法与数据结构任课教师签名 二维数A106采用行优先的存储方法，若每个元素4个存储单元，已知素A34的存储地址1000，则元A43的存储地址()A. 1020B.1024C.1036D.1240用二叉链表表示具n个结点的二叉树时，值为空的指针域的个数()出题教师签2011计算机合作联盟命题组审题教师签名A. n-1B.n+lC.nD.2n考试方式（ 闭 ）卷适用专业10 计科1-2考试时间（110）分钟题号题号得分一二三四五六七总分（注：判断题和选择题的答案写在答题纸上）一、单项选择题（每小题 2 分，共 30 分）与数据元素本身的形式、内容、相对位置、个数无

2、关的是数据(A.存储结构储存实现C.逻辑结构运算实现和qs所指结点之后插入上述链表应执行的语句为()A.q-next=s-next；s-next=p；B.s-next=p；q-next=s-next；C.p-next=s-next；s-next=q；D.s-next=q；p-next=s-next；队和栈的主要区别()A.逻辑结构不同存储结构不同C.所包含的运算个数不同限定插入和删除的位置不同二叉树中第5层上的结点个数最多()A.8B.16C.15D.32一棵完全二叉树上有1001 个结点，其中叶子结点的个数(A 250 500 254D501若无向G含21条边，G的顶点个数至少(A. 7B.

3、8C. 21D. 22若采用邻接矩阵法存储一个n 个顶点的无向图，则该邻接矩阵是一个(A. 上三角矩阵B. 稀疏矩阵C. 对角矩阵D. 对称矩阵以 v1 为起始结点对下图进行深度优先遍历，正确的遍历序列()Av1，v2，v3，v4，v5，v6，v7Cv1，v2，v3，v4，v7，v5，v6对表长为n查找长度()已知广义表的表头为a，表尾(b,c)，则此广义表(A.(a,(b,c)B.(a,b,c)C.(a),b,c)D.(a,b,c)n-1nn12B.2C. 2D.n32的有序表中进行二分查找，当查找成功时和给定值进行比较的关键1字个数最多()A. 4B. 5C.6D.71个元素为基准的一次划

4、分的结果为()A. (5，1，4，3，6，2，8，7)B.(5，1，4，3，2，6，7，8)C. (5，1，4，3，2，6，8，7)D.(8，7，6，5，4，3，2，1)15. 下列排序方法中稳定的为()冒泡排序B.堆排序C. 希尔排序D.快速排序 二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空1分，共20分）请在每个空格中填上正确答案。错填、不填均无分。数据元素及其关系在计算机存储器内的表示称。已知在结点个数大1的单循环链表中，指指向表中某个结点，则下列程段执行结束时，指q指向结*p的结点。q=p;while (q-next!=p) q=q-next;假设和X分别表示进栈和出

5、栈操作，由输入序列得到输出序列的操作序列则得的操作序列假设以行优先顺序将一阶的对角矩阵压缩存储到一维数中，则数Q大小至少。森林的中根遍历序列正是相应二叉树遍历序列，森林先根遍历序列正是相应二叉树遍历序列。一棵含999个结点的完全二叉树的深度。普里姆算法适用于网的最小生成树鲁斯卡尔）算法适用于网的最小生成树。三、解答题（本大题共 4 小题，每小题 7 分，共 28 分）a,b,c,d,e,f,g0110，10，110，111，00，011101001) (1)） (2) 和 9曼树的带权路径长度WPL。（2 分）Prim（顶点B出发）求如下连通图的最小生成树，要求：画出最小生（如第1V0V12

6、V3）。3从空树起，依次插入关键字 37，50，42，18，48，12，56，30，23，构造一棵二叉排序树。画出该二叉排序树（4分）画出从37（3分4016（Job,Fly,Man,Apple,Max,Key,Kid,Big,Lady,No,Set,Oct,Name）用线性探测再散列开放地址法处理冲突。并求在等概率情况下查找成功时的平均查8.在一个无向图中，所有顶点的度数之和等于所有边数倍9对于关键字序列49，38，65，97，76，13，进行 2-路归并升序排序，则第一找长度。设哈希函数为H(x)/（例如：）,其中 i 为关键字中趟归并排序的结果。10.若在线性表中采用二分查找法查找元素，

7、该线性表应该元素按值有序，且采用 存储结构。第一个字母在字母表中的序号(字母A 的序号为 1)。2四、算法阅读题（2 6 12 分）1. 设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。f4_1(&SS；（4分）f4_1中第（2分）void f4_1 (Stack *S)Queue Q; Stack T; int i=0;InitQueue(&Q); InitStack(&T); while(!StackEmpty(S)i+;if (i%2= =1) Push(&T,Pop(S); else EnQueue(&Q,Pop(S);while (!StackEmpty(&T) Push(

8、S,Pop(&T); while(!QueueEmpty(&Q) Push(S,DeQueue(&Q);typedef struct nodeDataTypestruct node * next; * LinkList;void f4_2( LinkList Ls )LinkList p, q;q = Ls-next;if ( q & q-next ) Ls-next = q-next; p=qwhile ( p-next )p = p-next; p-next = q;q-next = NULL;请回答下列问题：当Ls（4分）请简述算法的功能（2分）五、算法设计题（本题 10 分）假设以带头

9、结点的单链表表示有序表(非递减排列)，单链表的类型定义如下：typedef struct node DataType data; struct node *nextLinkNode, *LinkList;编写算法，从有序表A 中删除所有和有序表B 中元素相同的结点。算法的函数原型给定为：voidf5(LinkList A,LinkList 32011-2012 学年第一学期期末考试试题 （A）卷算法与数据结构参考答案及评分标准1112131415DC1112131415DCCCA12345678910CADBABBDBB二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格分，共20

10、分）请在每个空格中填上正确答案。错填、不填均无分。果 1 分；哈夫曼树 5 分，每对 3 个关键字得 2 分）gWPL=3*4+35*2+13*3+15*3+20*2+4*5+9*3=2531 存储结构3. XSX1 存储结构3. XSXSXSXXB5.2A7.3顶点：D9. 8 697 37E2 直接前驱10顶点：E8. 210.顺序G5顶点：E顶点：H6顶点：E顶点：C三、解答题（本大题共4小题，每7顶点：D顶点：F小题7分，共28分）1. （WPL 21最小生成树为：BBCAEDFGH44b3.(1) 4211211118910111213141516MaxKidLayNoSetOctN

11、ame24553685121211118910111213141516MaxKidLayNoSetOctName245536837185012371850123042562348 13 3.08(2) 331四、算法阅读题（本大题共2小题，每小题6分，共12分）1. （1）S=(1,3,5,7,6,4,2),其中2为栈顶元素；(4分)42将栈S偶数次出栈的元素入队列Q。(2分)30183018501223425648123048502.(1) 执行函数f4_2（4分）/2/23451LS或23(2)如果单链表LS中的元素个数不少于2一个结点后面。（2分）4.（ASL 21153键字得 1 分）001234567AppleBigFlyJobKeyMan五、算法设计题（本题10分）void f5(LinkList A,LinkList B)5