(完整版)数据结构考试试题(带答案)

1、系别 班次 学号 姓名XX科技大学成都学院二零零八至二零零九学年第一学期数据结构 课堂测试（60分钟） 闭卷 考试时间:题号一一二总分评卷教师分数一.填空题（每空2分，共40分）；1 .数据结构算法中，通常用时间复杂度和 空间复杂度_两种方法衡量其效率。2 .下面程序段的时间复杂度为 O（n2）。（n>1）for（i = 1;i<=n; i+）for（j = 1；j<= i；j+） x = x+1;3 .静态链表中指针表示的是 下一结点的地址。4 .线型表、栈和队列都是 线型结构，可以在线型表的 任意_位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾 插

2、入元素和队头删除元素。5 .在具有n个单元的循环队列中，队满时共有 n-1 个元素。6 .在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向 后移动n-i+1_个元素。7 .在n个结点的单链表中要删除已知结点*p，需找到它的 前驱 o8 .带有一个头结点的单链表 head为空的条件是 head->next=NULL。9 .在栈顶指针为hs的链栈中，判断栈空的条件是 hs= =NULL 10 .在hq的链队列中，判定只有一个结点的条件是_hq.front->next=hq.rear。11 .非空的循环单链表head的尾结点（由p指向），满足条件

3、p->next=head。12 .两个用相等的充分必要条件是 串长相等且对应字符相等 o13 .空用是长度为0的用,其长度等于0。14 .空格用是 由空格字符组成的用 ,其长度等于空格的个数.单项选择题（每题2分，共30分）；（说明：请将答案填入下表中）1 .若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A.顺序表B .双链表 C .带头结点的双循环链表D .单循环链表2 .设既、a2、a3为3个结点，则如下的链式存储结构称为： A表兀编P结点表元间关系1a132a213a32A.循环链表 B.单链表 C.双向循环链表D.双向链

4、表3 .有六个元素6, 5, 4, 3, 2, 1的顺序进栈，问下列哪一个不是合法的出栈序列？ （B ）A.5436 1 2B.34652 1C.453 1 26D.234 1 564 .若栈采用顺序存储方式存储，现两栈共享空间V1.m ,topi代表第i个栈（i=1,2） 栈顶，栈1的底在v1,栈2的底在Vm,则栈满的条件是（B ）。A.top2-top1|=0B.top1+1=top2C.top1+top2=mD.top1=top25 .数组Q n用来表示一个循环队列，front为当前队列头元素的前一位置，rear 为队尾元素的位置，假定队列中元素的个数小于n ,计算队列中元素的公式为（D

5、） A. rear front B.（n +front rear） %nC. n+rearfront D. （n+rear front ） % n6 .设栈S和队列Q的初始状态为空，元素e1, e2, e3, e4,e5和e6依次通过栈S, 一个元素出栈后即进队列 Q,若6个元素出队的序列是e2, e4,e6,e5 , e3,e1则 栈S的容量至少应该是（B）。A. 6 B. 4 C. 3 D. 27 .在数据结构中，从逻辑上可以把数据结构分成（C） o8 . A .动态结构和静态结构B .紧凑结构和非紧凑结构9 . C .线性结构和非线性结构D .内部结构和外部结构10 .判定一个顺序栈ST

6、 （最多元素为ND为空的条件是（B ）A. ST. top ! = ST.baseC. ST. top ! =ND11. 一个队列的入列序列是1, 2,A. 4,3,2,1 B . 1,2,3,4 CB. ST. top=ST.base.ST. top=N3, 4,则队列的输出序列是 B.1,4,3,2 D . 3,2,4,112 .判定一个循环队列QU(»多元素为N)为空的条件是 C 。A. QU.front= (QU.rear+1) %N B . QU.front ! = (QU.rear+1) %NC. QU.front= QU.rearD. QU.front ! = QU.r

7、ear13 .判定一个循环队列QU(最多元素为m。为满队列的条件是 A 。A. QU.front= (QU.rear+1) %N B. QU.front ! = (QU.rear+1) %NC. QU.front= QU.rearD. QU.front ! = QU.rear+114 .不带头结点的单链表head为空的判定条件是AA. head=NULL B . head - >next=NULL C . head- >next=headD. head!=NULL15 . 15.在双向链表指针p的结点前插入一个指针q的结点操作是(C)。A. p->Llink=q;q->

8、Rlink=p;p->Llink->Rlink=q;q->Llink=q；B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;16 .从一个具有n个结点的单链表中查找其值等于 x结

9、点时，在查找成功的情况下， 需平均比较D，结点。A. nB. n/2C. (n1)/2D. (n+1)/217 .设用 s1= 'ABCDEFG,s2='PQRST',函数 con(x,y)返回 x 和 y 用的连接用，subs(s,i,j )返回用s的从序号i的字符开始的j个字符组成向字用，len(s)返回 用 s 的长度，贝 con(subs(s1,2,len(s2), subs(s1,len(s2),2) 的结果用是 D A) BCDEF B ) BCDEFG C) BCPQRST D) BCDEFEF三.综合题(每题6分，共30分)1 .线性表具有两种存储方式，

10、即顺序方式和链接方式。现有一个具有五个元素的线性表L=23, 17, 47, 05, 31,若它以单链表方式存储在下列100119号地址空间中，每个结点由数据(占2个字节)和指针(占2个字节，由大写字母表示) 组成，如下所示：10012047p23q05r31s17t其中指针p, q, r, s, t的值分别为多少？该线性表的首结点起始地址为多少？末 结点的起始地址为多少？(共6分)2 . 答：p= 108 q =116r =112s= 0 或NULLt= 100首址=104末址二112 。3 .如果想将输入的一个字符序列逆序输出，如输入“ abcdef"，输出“ fedcba”，请

11、 分析用线性表、堆栈和队列等方式正确输出的可能性？(共6分)线性表是随机存储，可以实现，靠循环变量(j-)从表尾开始打印输出； 堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可； 队列是先进先出，不易实现。4 .写出删除顺序表中第i个元素的算法：(共6分)Status ListDelete_sq(SqList &L, int i, ElemType &e)Status del_sqllist(SqList &L,int i, ElemType &e)if (i < 1 II i > L.length) return ERROR;e= L.elem

12、i;for (j=i+1;j<= L.length;j+)L.elemj-1= L.elemj;-L.length;return OK;5 .写出顺序栈的入栈算法(共6分)Status Push(SqStack &S, SelemType e) void Push ( Stack &S, ElemType e ) 在栈顶之上插入元素e为新的栈顶元素p = new LNode ; /建新的结点 if(!p) exit(1) ; /存储分配失败 p -> data = e;p->next=S.top ;/链接到原来的栈顶S.top = p; /移动栈顶指针 +S.

13、length; /栈的长度增1 / Push6 .写出链队列的出队列算法(共6分)Status DeQueue(LinkQueue &Q, QelemType &e)Status DeQueue (LinkQueue &Q, QElemType &e) 若队列不空，则删除Q的队头元素，/用e返回其值，并返回OK;否则返回ERRORif (Q.front = Q.rear) return ERROR;p = Q.front->next; e = p->data;Q.front->next = p->next;if (Q.rear = p)

14、Q.rear = Q.front;free (p); return OK;第13页共14页XX科技大学成都学院20082009学年第一学期中期试题一一数据结构答案填空题（每题2分，共40分）；题号参考答案1空间复杂度2O(n2)3下一结点的地址4线型，任意，栈顶，队尾，队头5n-16n-i+17前驱8head->next= =NULL9hs= =NULL10hq.front->next=hq.rear11p->next=head12节长相等且对应字符相等13长度为0的申，014由空格字符组成的申，空格的个数.单项选择题（每题2分，共30分）;题号12345678910答案AA

15、BBDBCBBC题号1112131415答案AACDD.综合题（共30分）7 . p= 108 q =116r =112s= 0 或 NULt= 100首址二 104 末址二 112 。8 .线性表是随机存储，可以实现，靠循环变量（j-）从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。3. Status del_sqllist(SqList &L,int i, ElemType &e)if (i < 1 II i > L.length) return ERROR;e= L.elemi;for (j=i+1;j<

16、;= L.length;j+)L.elemj-1= L.elemj;-L.length;return OK;4.void Push ( Stack &S, ElemType e )在栈顶之上插入元素e为新的栈顶元素p = new LNode ; /建新的结点if(!p) exit(1) ; /存储分配失败p -> data = e;p->next=S.top ;/链接到原来的栈顶S.top = p; /移动栈顶指针+S.length; /栈的长度增1 / Push5. Status DeQueue (LinkQueue &Q, QElemType &e) 若

17、队列不空，则删除Q的队头元素，/用e返回其值，并返回OK;否则返回ERRORif (Q.front = Q.rear) return ERROR;p = Q.front->next; e = p->data;Q.front->next = p->next;if (Q.rear = p) Q.rear = Q.front;free (p); return OK;全真模拟试题（一）1、 单项选择题（在每小题的4个备选答案中，选出正确的答案，并将其号码填在 题干的括号内。每小题2分，共24分）1 .若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用 （4

18、）存储方式最节省时间。单链表 双链表 单向循环 顺序表2 .申是任意有限个（1）符号构成的序列 符号构成的集合字符构成的序列 字符构成的集合3 .设矩阵A （aj , l <i,j亨1 西素满足：aj w0（i 刁，l <i, j < 10）aj=0 （i<j, l<i, j < 10）现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A95的首址为23402336 2164 21604 .如果以链表作为栈的存储结构，则退栈操作时（）必须判别栈是否满对栈不作任何判别必须判别栈是否空判别栈元素的类型5 .设数组Da

19、ta0.m作为循环队列SQ的存储空间，front为队头指针，rear为队尾 指针，则执行出队操作的语句为（） front=front+1 front=（front+1）% m rear=（rear+1）%m front=（front+1）%（m+1）6 .深度为6 （根的层次为1）的二叉树至多有（）结点。 643231637 .将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号， 根结点的编号为1 o编号为49的结点X的双杀编号为（）242523无法确定8 .设有一个无向图G= （V, E）和G'二（V', E'）如果G'为G的生成树，则下

20、面不 正确的说法是（）G为G的子图G为G的边通分量G为G的极小连通子图且 V' =VG为G的一个无环子图9 .用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（）定都是同义词一定都不是同义词都相同不一定都是同义词10 .二分查找要求被查找的表是（3 ）键值有序的链接表链接表但键值不一定有序键值有序的顺序表顺序表但键值不一定有序11 .当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（） n2 nlog2n log2n n-112 .堆是一个键值序列ki,k2,，k,对i=1,2,|_n/2诵足（） ki w 2W 2i+i ki<k2i+1

21、 <k2iki&2i 且 kW2i+1（2i+1 < n）®ki 0 2i 或 ki 0 2i+1（2i+1 < n）2、 判断题（判断下列各题是否正确，正确在括号内打“V',错的找“X”。每小题1分，共10分）1 .双链表中至多只有一个结点的后继指针为空。（）2 .在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元 素，队列为满的条件是front= rear。（）3 .对链表进行插入和删除操作时，不必移动结点。（）4 .栈可以作为实现程序设计语言过程调用时的一种数据结构。（）5 .在一个有向图的拓朴序列中，若顶点 a在

22、顶点b之前，则图中必有一条弧<a,b>。（）i6 .对有向图G,如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每 个顶点，则该图一定是完全图。（）7 . 顺序查找法”是指在顺序表上进行查找的方法。（）8 .向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。 （）9 .键值序列A, C, D, E, F, E, F是一个堆。10 .二路归并时，被归并的两个子序列中的关键字个数一定要相等。（）3、 填空题（每空2分，共24分）1 .设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是; r=s; r->next=nu

23、ll;。2 .在单链表中，指针p所指结点为最后一个结点的条件是。3 .设一个链栈的栈顶指针是ls,栈中结点格式为info | link，栈空的条件是 如果栈不为空，则退栈操作为 p=ls； ; free（p）;。4 .已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结 点，则该树中有 个叶子的结点。5 .树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和 6 . N个顶点的连通图的生成树有 条边。7 . 一个有向图G中若有弧<vi,vj>、<vj,vk>ft<vi,vk>,则在图G的拓扑序列中，顶点vi ,vj和 vk的相对位置为 8

24、 .设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和 归并排序方法对其进行(按递增排序)，最省时间，最费时间。9 .下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内 容。typedef struct pnodeint key;struct pnode *left, *right;pnode;void searchinsert(int x, pnode t ) /*t 为二叉排序树根结点的指针 * /if ()p=malloc(size);p->key=x;p->lchild=null;p->rchild=null;t=p; else

25、 if (x<t->key) searchinsert(x,t->lchild) else;4、 应用题(本题共2 8分)1 .树的后根遍历方法是：若树非空则(4分)(1)依据次后根遍历根的各个子树T 1, T 2,Tm;(2)访问根结点2 .将下图的森林转换为二叉树。(4分)3 .下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。(4分)图7.11遍历无向图(a)无向图G6 (b)深度优先搜索示例(c) G 6的邻接表表示(c)表头结点4 .已知一个无向图的

26、邻接表如下图所示。(本题4分，每小题2分)(1)画出这个图。(2)以vi为出发点，对图进行广度优先搜索，写出所有可能的访问序歹上5 .设n个元素的有序表为R, K为一个给定的值，二分查找算法如下：int binsearch(sqlist R, keytype K)j=1;h=n ;suc=0;while(j<=h)&&(!suc)mid =(j+h)/2;switchcase K=Rmid.key: suc=1; break;case K<Rmid.key: h=mid-1; break;case K>Rmid.key: j=mid+1if (suc) ret

27、urn(mid); else return(0);将上述算法中划线语句改为：K<Rmid.key: h=mid.(1 )改动后，算法能否正常工作？请说明原因。(2)若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；若能正常工作，请给出一个查找序列和查找某个键值的比较次数。(本题6分，每小题3分)6.有一组键值25, 84, 21, 47, 15, 27, 68, 35, 24,采用快速排序方法由小到大进行排序，请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。(本题6分)五、设计题(共14分)1 .设棵二叉树以二叉链表为存储结构，结点结构为lchild |data |

28、rchild 。设计一个算法，求在前根序列中处于第k个位置的结点。(本题6分)2 .设某单链表L的结点结构为data |next试画出该链表的结构图，并用类C语言编写算法判断该链表的元素是否是递增的。(本题8分)全真模拟试题(一)参考答案、单项选择题123 分析：按题意，矩阵A是个三角矩阵，A I,j的首地址可用下列公式计算：LOC (a) =LOC(a11)+(k-1)*L其中K为AI,j在A中的序号k=I*(I-1)/2+j , L为每个元素所占的单元数。所以有：LOC (aj) =2000+ (9* (9-1) /2+5-1) *4=2000+160=2160。故为答案4 .5 .6 .

29、7 .8 .分析：如果G'为G的生成树，那么G'是G的子图，也是G的无环子图，并 且还是G的极小连通子图，且 V' =V,而连通分量则是指无向图的极大连通子图。故 答案是错误的。9 .10。11。12。二、判断题1.v 2.x 3.v 4.v 5.x 6.x 7.x 8.v 9.v 10.x三、填空题1. R->next =s.2. P->next= = NULL3. Ls= =NULL 、ls=ls->link.4. 12 分析：设 n1=2,n2=3,n3=4,树的总结点数为n=n0+ n1+n2+n3树的分支数为 n-1= n+2n2+3n3-得：-1= n2+2n3-no有 n0=n2+2n3+1=3+2*4+1=125. 双亲表示法。6. N-17. I,j,k.8. 冒泡排序、快速排序9. T= =NULL、searc