《数据结构考试试题(带答案)》由会员分享，可在线阅读，更多相关《数据结构考试试题(带答案)（14页珍藏版）》请在金锄头文库上搜索。
1、科技大学成都学院二零零八至二零零九学年第一学期 数据结构 课堂测试（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. 线型表、栈和队列都是_线型_结构，可以在线型表的_任意_位置插入和删除元素；对于栈只能在_栈顶_插入和删除元素；对于队列只能在_队尾_插入元素和_队头_删
2、除元素。5. 在具有n个单元的循环队列中，队满时共有_n-1_个元素。6. 在一个长度为n 的顺序表中第i 个元素（1=inext= =NULL_。9. 在栈顶指针为hs的链栈中，判断栈空的条件是_hs= =NULL_。10. 在hq的链队列中，判定只有一个结点的条件是_hq.front-next=hq.rear_。11. 非空的循环单链表head的尾结点（由p指向），满足条件_p-next=head。12. 两个串相等的充分必要条件是_串长相等且对应字符相等_。13. 空串是_长度为0的串_，其长度等于_0_。14. 空格串是_由空格字符组成的串_， 其长度等于_空格的个数_ 。二单项选择题
3、（每题2分，共30分）；（说明：请将答案填入下表中）题号12345678910答案AABBDBCBBC题号1112131415答案AACDD1. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表2. 设a1、a2、a3为3个结点，则如下的链式存储结构称为：A表元编号结点表元间关系1a132a213a32A循环链表 B单链表 C双向循环链表 D双向链表3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（B ）A. 5 4 3 6 1 2 B. 3 4
4、 6 5 2 1 C. 4 5 3 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|=0 B. top1+1=top2 C. top1+top2=m D. top1=top25. 数组用来表示一个循环队列，front为当前队列头元素的前一位置，rear为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为(D)A. rearfront B.（nfrontrear）% nC. nrearfront D.（n
5、rearfront）% 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）。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构8. 判定一个顺序栈ST（最多元素为N）为空的条件是 （B ）。ASTtop ！= ST.baseBSTtop=ST.baseCSTtop！=N DSTtop=N9. 一个队
6、列的入列序列是1，2，3，4，则队列的输出序列是 B 。A4,3,2,1 B1,2,3,4 C1,4,3,2 D3,2,4,110. 判定一个循环队列QU(最多元素为N)为空的条件是 C 。AQU.front= （QU.rear+1）%N BQU.front！= （QU.rear+1）%NCQU.front= QU.rear DQU.front！= QU.rear 11. 判定一个循环队列QU（最多元素为m0）为满队列的条件是 A 。AQU.front= （QU.rear+1）%N BQU.front！= （QU.rear+1）%NCQU.front= QU.rear DQU.front！=
7、QU.rear+112. 不带头结点的单链表head为空的判定条件是 A Ahead=NULL Bhead - next=NULL Chead- next=head Dhead!=NULL13. 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-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Lli
8、nk=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_D_个结点。AnBn/2C(n1)/2D(n+1)/215. 设串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三综合
9、题（每题6分，共30分）1. 线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L=23，17，47，05，31，若它以单链表方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节,由大写字母表示）组成，如下所示：其中指针p，q，r，s，t的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？(共6分)2. 答：p= 108 q = 116 r = 112 s= 0 或NULL t= 100 首址= 104 末址= 112 。3. 如果想将输入的一个字符序列逆序输出，如输入“abcdef ”，输出“fedcba”，请分析
10、用线性表、堆栈和队列等方式正确输出的可能性？ (共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 L.length) return ERROR; e= L.elemi; for (j=i+1;j data = e; p-next=S.
11、top ;/ 链接到原来的栈顶S.top = p; / 移动栈顶指针+S.length;/ 栈的长度增1 / Push6. 写出链队列的出队列算法(共6分)Status DeQueue(LinkQueue &Q, QelemType &e) Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回OK；否则返回ERROR if (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;科技大学成都学院20082009学年第一学期中期试题数据结构答案一 填空题（每题2分，共40分）；题号参考答案1空间复杂度2O(n2)3下一结点的地址4线型，任意，栈顶，队尾，队头5n-16n-i+17前驱8head-next= =NULL9hs= =NULL10hq.front-next=hq.rear11p-next=head12串长相等且对应字符相等13长度为0的串，0
