数据结构期中试题及参考答案

淮 海 工 学 院 2009 - 2010 学年 第 1 学期 数据结构期中试卷 ( 闭卷)题号一二三四五六七八九总 分得分 一、单项选择题（本大题共12小题，每小题2分，共24分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。选错、多选或未选均无分。1.按值可分解，数据类型通常可分为两类，他们是【 C 】A静态类型和动态类型B. 原子类型和表类型C原子类型和结构类型D. 数据类型和指针类型2.对于三个函数f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008和h(n)=8888nlogn+3n2，下列陈述中不成立的是【C 】A. f(n)是O(g(n)B. g(n)是O(f(n)C. h(n)是O(nlogn) D. h(n)是O(n2)3.指针p、q和r依次指向某循环链表中三个相邻的节点，交换节点*q和节点*r在表中的次序的程序段是 【 A 】A. p-next=r; q-next=r-next; r-next=q;B. p-next=r; r-next=q; q-next=r-next;C. r-next=q; q-next=r-next; p-next=r;D. r-next=q; p-next=r; q-next=r-next;4.若进栈次序为 a ,b ,c,且进栈和出站可以穿插进行，则可能出现的含个元素的出站序列个数是 【 B 】A3B5C6 D75.假设以数组An存放循环队列的元素，其头指针front指向队头元素的前一个位置、为指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 【 D 】Arear=frontB. (front+1)%n=rearC. rear+1=frontD.(rear+1)%n=front6.串的操作函数str定义为：int str (char *s) char *p=s;while (*p!=0)p+;return p-s;则str(“abcde”)的返回值是 【 C 】A3B4C5 D67.二维数组A106采用行优先的存储方法，若每个元素占4个存储单元，已知元素A34的存储地址为1000，则元素A43的存储地址为 【 A 】A1020B1024C1036D12408.对广义表L=(a,()执行操作tail(L)的结果是 【 B 】A()B()Ca D(a)9.已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为 【 A】A. FEDCBAB. ABCDEFC. FDECBAD. FBDCEA10.已知森林F=T1, T2, T3, T4, T5,各棵树Ti(i=1，2，3，4，5)中所含节点的个数分别为7，3，5，1，2，则与F对应的二叉树的右子树种的节点个数为 【 D 】A2B3C8 D1111.若非连通无向图G含有21条边，则G的顶点个数至少为 【 B 】 题12图A7B8C21 D2212.如图所示的有向图的拓扑序列是 【 B 】A. c , d , b , a , e B. c , a , d , b , ecC. c , d , e , a , bD. c , a , b , d , e二、填空题(本大题7小题，每题2分，若有两个空，每个空格1分，共14分)请在每个空格中填上正确答案。错填、不填均无分。1.数据的链式存储结构的特点是借助 指示元素存储地址的指针 表示数据元素之间的逻辑关系。2.如果需要对线性表频繁进行 插入 或删除操作，则不宜采用顺序存储结构。 top1 top2 0 n-1 栈1 栈23.如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是top1=0，栈2为空的条件是top2=n+1，则“栈满”的判定条件是top1=top2+1 。4.静态存储分配的顺序串在进行插入、置换和连接等操作时可能发生越界。5.广义表L=(a，(b，()的深度为3。6.任意一棵完全二叉树中，度为1的节点数最多为1。7.求最小生成树的克鲁斯卡尔算法耗用的时间与图中边的数目正相关。三、解答题（本大题共4小题，每小题8分，共24分）5 4 3 1.如图所示，在nn矩阵A中，所有下标值满足关系式i+jn+1的元素aij的值均为0，现将A中其他元素按行优先顺序依次存储到长度为n(n+1)/2的一维数组sa中，其中元素a1n存储在sa0。（1）设n=10，元素a4,9存储在sap，写出下标p的值；p=8（2）设元素aij存储在sak中，写出有i,j和n计算k的一般公式。 0 0 0 a1,n0 a2,n-1 a2,n 0an-1,2an,1an,2 an-1,n an,n题3-1图 k=i(i-1)/2+j+i-n-12.由字符集s，t，a，e，i及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。iseat10101010eatst 题3-2图3.已知无向图G的邻接表如图所示，（1）画出该无向图；（2）画出该图的广度优先生成森林。2212548873 100022766 题3-3图012345678ABCDEFGHI四、算法阅读题（本大题共3小题，每题8分，共24分）1.阅读下列算法，并回答问题：（1） 无向图G如图所示，写出算法f30(&G)的返回值；k=3BCDAGFH（2）简述算法f30的功能。求图中连通分量的数目#define MaxNum 20int visitedMaxNum;void DFS(Graph *g,inti);/*从顶点Vi出发进行深度优先搜索，访问顶点Vj时置visitedj为1*/int f30(Graph *g)Int i,k;for (i=0;I n; i+) /*g-n为图g的定点数目*/visitedi=0;for (i=k=0; I n; i+)if (visitedi=0)K+;DFS(g,i);returnk;2.假设学生成绩按学号增序从年初在带头结点的单链表中，类型定义如下：typedefstructNodeint id; /*学号*/int score;/*成绩*/structNode*next;LNode,*LinkList;idscorenext阅读算法f31，并回答问题；（1）设节点结构为 ,成绩链表A和B如图所示，画出执行算法f31(A,B)后节点A所指的链表；170556448390240A575465238B 题31图（2）减速算法f31的功能。Void f31(LinkList A, LinkList B)LinkListp,q;p = A-next;q = B-next;while (p & q)if(p-id id)p = p -next;else if(p-if q- id)q =q next;elseif (p-score score score = q-score;elsep-score = 60;p = p-next;q = q-next;3.阅读下列算法，并回答问题：（1）设串s=“OneWorldOneDream”，t=“One”，pos是一维整型数组，写出算法f32(s,t,pos)执行之后得到的返回值和pos中的值；（2）简述算法f32的功能。int str(char *s);/*返回串s的长度*/int index(char *st, char *t);/*若串t在串st中出现，则返回在串st中首次出现的下标值，否则返回-1*/int f32(char *s, char *t, int pos)int i,j,k,ls,lt;ls = strlen(s);lt = strlen(t);if(ls = 0| lt=0)return -1;k=0;i=0;doj=index(s+I,t);if(j=0)Posk+=i+j;I + = j + lt ;while (i+lt =0);Return k;五、算法设计题（本题14分）34.假设线性表采用顺序存储结构，其类型定义如下：#define ListSize 100typedef structint dataListSize;int length; SeqList, *Table;编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。