数据结构试题.doc

数据结构期中考试题学号 姓名 得分 一、 单选题（每空3分，共18分）1、 在一个单链表HL中,若要向q所指结点之后插入一个指针p指向的结点,则执行 .A. HL=p; p-next=HLB. P-next=HL; HL=pC. P-next=q-next; q-next=pD. P-next=q-next; q=p-next2、 从一个二维数组bmn中找出最大值元素的时间复杂度为A. m B. n C. m+n D. mn3、 当利用大小为N的数组顺序存储一个栈时，如果使用top=0表示栈空，那么该栈最多可保存_个数据。A. NB. N+1C. N-1 D. 04、 假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为A. front = rear B. front != NULLC. rear != NULL D. front = NULL5、 树结构中，前驱结点与后继结点之间存在_关系A. 一对一 B. 一对多 C. 多对一 D. 多对多6、 在以下时间复杂度的数量级中，数量级最大的是A. B. C. D. 二、 填空题（每空2分，共32分）1、 抽象数据类型由_与_两部分构成。2、 向一个长度为n的有序单链表中插入一个元素时，为寻找插入位置需要平均比较_个元素。3、 在以HS为表头指针的单链表中，链表为空的条件分别为_。4、 在一个稀数矩阵的带行指针向量的链接存储中，每个元素结点包含_个域，其中_个指针域。5、 向一个链栈插入p所指向的结点时，需要把栈顶指针的值赋给p所指向的结点的_，然后把p赋给_。6、 在用一维数组AN存储一个顺序循环队列时，若队列的队首、尾指针分别用f和r表示，则对列长度为_。7、 中缀表达式5+2*(y-1)/2的后缀表达式为_。8、 在数据结构中，数据的逻辑结构有线性结构、图结构、_、_四种，物理实现上有顺序结构、索引结构、_、_四种。9、 在带表头附加结点的线性链表HL中，链表为空的条件为_。10、 通常，评价一个算法有正确性、健壮性、_、时间复杂度、空间复杂度五个方面。三、阅读算法，回答问题（10分）1、 void AE(Stack&S)InitStack(S);Push(S,30);Push(S,20*2);Push(S,15);Int x=3*Pop(S)+Pop(S);Push(S,x);int i,a4=5,9,18,15;x=0;For (i=0;i4;i+)Push(S,ai);x+=ai;Push(S,x);While(! StackEmpty(S)coutPop(S) ;该算法被调用后输出结果为：六、编写算法（30分）1、 根据一个元素类型为整型的单链表生成两个单链表，使得第一个单链表中包含原单链表中所有元素值为奇数的结点、第二个单链表中包含原单链表中所有元素值为偶数的结点，而原单链表保持不变。（10分）2、 编写把十进制整数转换为十六进制数输出的算法。（15分）3、 从线性表中删除所有其值重复的元素，使得