数据结构中期考试(试题) 电子科技大学.doc

系别 班次 学号 姓名 .密封线以内答题无效电子科技大学成都学院二零零八至二零零九学年第一学期 数据结构 课堂测试（60分钟） 闭卷 考试时间：题号一二三总分评卷教师分数一填空题（每空2分，共40分）；1. 数据结构算法中，通常用时间复杂度和_两种方法衡量其效率。2. 下面程序段的时间复杂度为_。(n1) for(i = 1; i = n; i+)for(j = 1; j = i; j+) x = x + 1; 3. 静态链表中指针表示的是_。4. 线型表、栈和队列都是_结构，可以在线型表的_位置插入和删除元素；对于栈只能在_插入和删除元素；对于队列只能在_插入元素和_删除元素。5. 在具有n个单元的循环队列中，队满时共有_个元素。6. 在一个长度为n 的顺序表中第i 个元素（1=inext=NULL Chead- next=head Dhead!=NULL13. 15.在双向链表指针p 的结点前插入一个指针q 的结点操作是（ ）。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-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。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)的结果串是A）BCDEF B）BCDEFG C）BCPQRST D）BCDEFEF三综合题（每题6分，共30分）1. 线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L=23，17，47，05，31，若它以单链表方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节,由大写字母表示）组成，如下所示：其中指针p，q，r，s，t的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？(共6分)答：p= q = r = s= t= 首址= 末址= 2. 如果想将输入的一个字符序列逆序输出，如输入“abcdef ”，输出“fedcba”，请分析用线性表、堆栈和队列等方式正确输出的可能性？ (共6分)3. 写出删除顺序表中第i个元素的算法：(共6分)Status ListDelete_sq(SqList &L, int i, ElemType &e)4. 写出顺序栈的入栈算法(共6分)Status Push(SqStack &S, SelemType e)5.