@数据结构复习题

ENDP；{ODD_EVEN}

【经典考题】 数据结构是研究数据的 和 ，以及它们之间的相互关系，并对这种结构定义相应的 ，设计出相应的 ，而确保经过这些运算后所得到的新结构是 结构类型。

解：本部分基本上都是概念试题。

参考答案依次为：物理结构、逻辑结构、运算、算法、原来的。

【经典考题】 在数据结构中，与所使用的计算机无关的数据叫A结构：链表是一种采用B存储结构存储的线性表；链表适用于C查找；在链表中进行D操作的效率比在顺序存储结构中进行D操作效率高；二分查找E存储结构。供选择的答案：

A)①存储 ②物理 ③逻辑 ④物理和逻辑 B)①顺序 ②网状 ③星式 ④链式

C)①顺序 ②二分法 ③顺序，也能二分法 ④随机 D)①二分法查找 ②快速查找 ③顺序查找 ④插入

E)①只适用于链式 ②只适用于顺序 ③既适用于顺序也适用于链式

④既不适用于顺序也不适用于链式

解：本题旨在考察基本的概念。

答案为：A) ③；B)④；C)①；D)④；E)②。

【经典考题】 在双向链表存储结构中，删除

P所指的结点时，需修改指针( )。

A)(P->llink)->rlink=P->rlink B)P->llink=(P->llink)->llink (P->rlink)->llink=P->llink ((P->llink)->llink)—>rlink=P C) ((P->llink)->llink)->rlink=P D) ((P->rlink)->rlink)->llink=P

P->llink=(P->llink)->llink P->rlink=(P->rlink)->rlink

解：答案为A)。 考虑在P所指结点后或前插入一结点的应如何做？

【经典考题】 根据线性表的链式存储结构形式，每个结点所含指针的个数，链表可分为A和B：而根据

指针的连接方式，链表又可分为C和D。

解：A：单链表； B：多重链表； C：循环链表； D：普通链表。

【经典考题】 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为 。

解：O(n)。

【经典考题】 (1)写出在双向链表中，在指针P所指结点前面插入一个结点*S的语句序列。

(2)写出带头结点的双向循环链表L为空表的条件。

解：(1) S->Prior=P->Prior； P->Prior->Next=S；

S->Next=P； P->Prior=S；

(2) (L= =L->Next)&&(L= =L->Pnor) 考虑不带头结点的双向循环链表L为空表的条件？

【经典考题】将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 ( )。

A)n B)2n-1 C)2n D)n-1 解：答案为A)

〖栈和队列〗

解答题3、设循环队列cq的队首指针为front,队尾指针为rear,队列可容纳的最大元素个数为max，分别用下列三种方法来区分队满或队空，试在表中写入相应的处理。（5分） 初始空队列各变量初值 出队前判队空条件 入队前判队满条件 出队时该方法的特殊处理 入队时该方法的特殊处理 用记数变量C记载元素个数 cq.fornt:=cq.rear:=0 C:=0 C=0 C=max cq.fornt:=(cq.fornt+1)%max C:=C-1 cq.rear:=(cq.rear+1)%max C:=C+1 用标志位 cq.fornt:=cq.rear:=0 tag:=0 tag=0 AND cq.fornt=cq.rear tag=1 AND cq.fornt=cq.rear 牺牲一个元素的存储单元 cq.fornt:=cq.rear:=0 cq.fornt=cq.rear (cq.rear+1)%max=cq.front cq.fornt:=(cq.fornt+1)%max cq.fornt:=(cq.front+1)%max IF cq.front=cq.rear THEN Tag:=0 cq.rear:=(cq.rear+1)%max IF cq.front=cq.rear THEN Tag:=1 cq.rear:=(cq.rear+1)%max

填空题3．递归过程实现时使用的数据结构是_栈，层次遍历二叉树时使用的数据结构是队列(2分)

不定项选择题3、一个队列的入队序列是a，b，c，d，则它的所有可能的出队序列是(2分)

①d，c，b，a ②a，d，c，b

③a，b，c，d ④c，b，d，a

答案：③

算法题2．利用两个栈S1和S2模拟一个队列，该队列如下图所示，试写出队空和队满条件，并编写出队列的插入add和删除delete运算。 (10分)

-m 0 1 n top1=front ← S1 S2 → top2=rear

PROC add(x：elementype) {将x插入到队尾中} IF top2=n THEN ERROR(‘ 队满’) ELSE [ top2:=top2+1; IF top2>0 THEN S2[top2]:=x ELSE S1[top2]:=x] ENDP；{add}

PROC delete(var x：elementype) {删除队首元素，并赋给x} IF top1>top2 THEN ERROR(‘队空’) ELSE [ IF top1<1 THEN x:=S1[top1 ] ELSE x:=S2[top1];

top1:=top1+1 ] ENDP;{delete}

【经典考题】一般情况下，将递归算法转换成等价的非递归算法应该设置( )。

A)栈 B)队列 C)堆栈或队列 D)数组

解：栈的用途之一就是将递归转换为非递归，选择A)。

【经典考题】若一个栈的输入序列是1，2，3，?，n，输出序列的第一个元素是n，

则第i个输出元素是( )。

A)n-i B)n-i+1 C)i D)n-i-1 解：答案为B)。

【经典考题】在用一维数组sequ[0…m-1]存储循环队列的元素时，怎样另设一个标志tag来区分尾指针(rear)和头指针(front)相等时队列的状态是“空”还是“满”?

解：设标志tag的初始值为“0”，如果由于元素入队列使得rear= =front时，则置tag为“1”：反之，如果由于元素出队列使得rear= =front成立，则可由标志tag的值来区别队列当前的状态是“满”还是“空”，即可决定其操作是否能进行。