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

《数据结构考试试题(带答案)》由会员分享，可在线阅读，更多相关《数据结构考试试题(带答案)（14页珍藏版）》请在装配图网上搜索。

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

2、n个单元的循环队列中，队满时共有 n-1个元素。6. 在一个长度为n的顺序表中第i个元素（1=inext=NULL。9. 在栈顶指针新S的链栈中，判断栈空的条件是hs=NULL 。10. 在hq的链队列中，判定只有一个结点的条件是hq.front-next=hq.rear 。11. 非空的循环单链表head的尾结点（由p指向），满足条件 p-next=head。12. 两个串相等的充分必要条件是 串长相等且对应字符相等。13. 空串是 长度为0的串 ，其长度等于0。14. 空格串是 由空格字符组成的串，其长度等于 空格的个数二.单项选择题（每题2分，共30分）；（说明：请将答案填入下表中）题号

3、12345678910答案AABBDBCBBC题号1112131415答案AACDD1. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运 算，则利用（A）存储方式最节省时间。A. 顺序表 B-双链表 C.带头结点的双循环链表D.单循环链表2. 设a1. a2、a3为3个结点，则如下的链式存储结构称为：A表元编号结点表元间关系1a132a213-032A.循环链表B.单链表C-双向循环链表。.双向链表3. 有六个元素6,5, 4, 3, 2, 1的顺序进栈，问下列哪一个不是合法的出栈序列？(B)A. 5 4 3 6 1 2 B. 3 4 6 5 2 1 C. 4 5 3

4、1 2 6 D. 2 3 4 1 5 64. 若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈(i =1,2) 栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是(B)。A. top2-top1|=0B. top1+1=top2C. top1+top2=mD. top1=top25. 数组Qn用来表示一个循环队列，front为当前队列头元素的前一位置，rear为队尾元素的位置，假定队列中元素的个数小于n,计算队列中元素的公式为(D) A. rear-frontB. (n+frontrear) % nC. n+rear frontD. (n+rear front) % n

5、6. 设栈S和队列Q的初始状态为空，元素e1, e2, e3, e4,e5和e6依次通过栈S, 一个元素出栈后即进队列Q,若6个元素出队的序列是e2, e4,e6,e5, e3,e 1则 栈S的容量至少应该是(B)。A. 6B. 4C. 3D. 27. 在数据结构中，从逻辑上可以把数据结构分成(C)。8. A.动态结构和静态结构B.紧凑结构和非紧凑结构9. C.线性结构和非线性结构D.内部结构和外部结构10. 判定一个顺序栈ST (最多元素为N)为空的条件是(B )。A. ST. top ! = ST.base B. ST. top=ST.baseC. ST. top! =ND. ST. to

6、p=N11. 一个队列的入列序列是1, 2, 3, 4,则队列的输出序列是 B 。A. 4,3,2,1 B. 1,2,3,4 C. 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.rear13. 判定一个循环队列QU(最多元素为m0)为满队列的条件是A 。A.QU.front= (QU.rear+1)%N B.QU.front!= (QU.rear+1)%N

7、C. 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-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-Lli

8、nk;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;16. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下， 需平均比较 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,l

9、en(s2),2)的结果串是 D A) BCDEF B) BCDEFG C) BCPQRST D) BCDEFEF三. 综合题(每题6分，共30分)1.线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线 性表L=23，17，47，05，31，若它以单链表方式存储在下列100119号地址 空间中，每个结点由数据(占2个字节)和指针(占2个字节，由大写字母表示) 组成，如下所示：10012047P23q05r31s17t其中指针p，q，r，s，t的值分别为多少？该线性表的首结点起始地址为多少？末 结点的起始地址为多少？(共6分)2. 答：p= 108 q =116r =112s

10、= 0 或NULLt= 100 首址=104 末址=112。3. 如果想将输入的一个字符序列逆序输出，如输入“ abcdef ”，输出“fedcba”，请分析用线性表、堆栈和队列等方式正确输出的可能性？(共6分)线性表是随机存储，可以实现，靠循环变量(j-)从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。4. 写出删除顺序表中第i个元素的算法：(共6分)Status ListDelete_sq(SqList &L, int i, ElemType &e)Status del_sqllist(SqList &L,int i, ElemType

11、&e)if (i L.length) return ERROR;e= L.elemi;for (j=i+1;j data = e;p-next=S.top ;/链接到原来的栈顶S.top = p; /移动栈顶指针+S.length; /栈的长度增1 / Push6. 写出链队列的出队列算法(共6分)Status DeQueue(LinkQueue &Q, QelemType &e)Status DeQueue (LinkQueue &Q, QElemType &e) /若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERRORif (Q.front = Q.rear) ret

12、urn 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;XX科技大学成都学院20082009学年第一学期中期试题数据结构答案一. 填空题（每题2分，共40分）；题号参考答案1空间复杂度2O(n2)3下一结点的地址4线型，任意，栈顶，队尾，队头5n-16n-i+17前驱8head-next= =NULL9hs= =NULL10hq.front-next=hq.rear11p-next=head12串长相等且对应字符相等13长度

13、为0的串，014由空格字符组成的串，空格的个数二.单项选择题（每题2分，共30分）;题号12345678910答案AABBDBCBBC题号1112131415答案AACDD三.综合题（共30分）7. p= 108 q =116 r =112s= 0 或 NULLt= 100首址=104末址=112。8. 线性表是随机存储，可以实现，靠循环变量（j-）从表尾开始打印输出； 堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。3. Status del_sqllist（SqList &L,int i, ElemType &e）if (i L.length) return

14、 ERROR;e= L.elemi;for (j=i+1;j data = e;p-next=S.top ;/链接到原来的栈顶S.top = p; /移动栈顶指针+S.length; /栈的长度增1 / Push4. 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) Q.rear

15、 = Q.front;free (p); return OK;全真模拟试题（一）一、单项选择题（在每小题的4个备选答案中，选出正确的答案，并将其号码填在题干的括号内。每小题2分，共24分）1. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用 （4 ）存储方式最节省时间。 单链表双链表单向循环 顺序表2. 串是任意有限个（1）符号构成的序列符号构成的集合字符构成的序列字符构成的集合3. 设矩阵A （aij , li,jj, li, j 10）aij=0 （ij, li, j 10）现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则

16、元素A95的首址为23402336 2164 21604. 如果以链表作为栈的存储结构，则退栈操作时（） 必须判别栈是否满 对栈不作任何判别 必须判别栈是否空 判别栈元素的类型5. 设数组Data0.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个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号， 根

17、结点的编号为1。编号为49的结点X的双亲编号为（）242523无法确定8. 设有一个无向图G= （V，E）和G= （V，E）如果G为G的生成树，则下面不 正确的说法是（）G为G的子图G为G的边通分量G为G的极小连通子图且V=VG为G的一个无环子图9. 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（）一定都是同义词一定都不是同义词都相同不一定都是同义词10. 二分查找要求被查找的表是（3 ）键值有序的链接表链接表但键值不一定有序键值有序的顺序表顺序表但键值不一定有序11. 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的 次数为（） n2 nlog2n l

18、og2n n-112. 堆是一个键值序列k,k2,., kn,对 i=1,2,.,|_n/2_|,满足（） k&Mk2i+1 kik2i+1k2ikik2i 且 kik2i+1（2i+1n）kik2i 或 kik2i+1（2i+1n）二、判断题（判断下列各题是否正确，正确在括号内打“V”，错的找，遂”。每小 题1分，共10分）1. 双链表中至多只有一个结点的后继指针为空。（）2. 在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元 素，队列为满的条件是front=rear0（）3. 对链表进行插入和删除操作时，不必移动结点。（）4. 栈可以作为实现程序设计语言过程

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

20、r=s; r-next=null;。2. 在单链表中，指针p所指结点为最后一个结点的条件是。3. 设一个链栈的栈顶指针是ls，栈中结点格式为info | link，栈空的条件是. 如果栈不为空，则退栈操作为p=ls； ； free（p）;。4. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有 个叶子的结点。5. 树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和.6. N个顶点的连通图的生成树有 条边。7. 一个有向图G中若有孤. 和,则在图G的拓扑序列中，顶点 Vi,vj和 vk的相对位置为。8. 设表中元素的初始状态是按键值递增的，分别用堆排序、快

21、速排序、冒泡排序和 归并排序方法对其进行(按递增排序)，最省时间，最费时间。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 if (xkey) searchinsert(x,t-lchild)else;四

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

23、。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 KRmid.key: j=mid+1if (suc) return(mid); else return(0);将上述算法中划线语句改为：Knext =s.2. P-next= = NULL3. Ls= =NULL、ls=ls-link.4. 12 分析： 设 n1=2,n2=3,n3=4,树

24、的总结点数为n=n0+ n1+n2+n3树的分支数为n-1= n1+2n2+3n3-得：-1= n2+2n3-n0有 n0=n2+2n3+1=3+2*4+1=125. 双亲表示法。6. N-17. I,j,k.8. 冒泡排序、快速排序9. T= =NULL、searchinsert(x,t-rchild).四、应用题1. EBFGCKHIJDAo2. 答案如图应用题I 9. 2.2所示。3. 3.分析：本题实际上是求最小生成树问题。由于衅中有两条权值为6的边，故 可以得到两种方案。答案如图应用题I 9. 3.2所示。4. 答案：(1) 答案如图应用题I 9. 4.2所示。(2) v1 v2 v

25、4 v5 v3 和 v1 v4 v2 v3 七。5. (1)经过改动以后，有可能出现死循环，比如当查找的键值K小于有序表中的最 小键值时，就会出现死循环。故算法不能正常进行。(2)假设有序表的查找序列为(2, 3, 4, 5, 6),当待查的键值K=1时，出现死 循环。6. 答案：25 84 21471527683524第趟2415 21254727683584第二趟2115 2425352747 6884第三趟1521 24252735476884得到1521 242527354768 84第一趟排序过程中键值的移动情况如下:第一趟：25 84 21471527683524 一次交换之后24

26、 84 21471527683525二次交换之后24 25 214715276835842425 21 4715276835842425 21 4715276835842425 21 471527683584三次交换之后24 15 214725276835842415 21 472527683584四次交换之后24 15 21254727683584以上“-”表示当前经比较不交换位置的元素。“ ”表示当前经比较交换位置的元素。五、设计题1. Bitreptr search(bitreptr t ,int k)if (t!=null)count+;if (count= =k)return (t);else search(t-lchild,k);search(t-rchild,k);2. 单链表L的结构如图设计题I 9. 2.2所示。Int isviser(lklist L)p=L;while(p-next!=null)if (p-data next-data) p=p-next;else return(0);return(1);