数据结构 试题及答案

1．在下面的程序段中，对x 的赋值语句的频度为（ ）C

FOR i:=1 TO n DO

FOR j:=1 TO n DO

x:=x+1;

A． O(2n) B．O(n) C．O(n2) D．O(log2n)

2. 静态链表中指针表示的是（ ）.C 

A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址

3．线性表（ a1,a2,…,an）以链接方式存储时，访问第i 位置元素的时间复杂性为（ ）C

A．O（i） B．O（1） C．O（n） D．O（i-1）

4． 双向链表中有两个指针域，llink 和rlink，分别指回前驱及后继，设p 指向链表中的一个结点，q指向一待插入结点，现要求在p 前插入q，则正确的插入为（ ）D

A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink;

B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink;

C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p;

D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q;

5. 双向链表中有两个指针域，llink 和rlink 分别指向前趋及后继，设p 指向链表中的一个结点，现要求删去p 所指结点，则正确的删除是（ ）（链中结点数大于2，p 不是第一个结点）D

A．p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink; dispose(p);

B．dispose(p); p^.llink^.rlink:=p^.llink; p^.llink^,rlink:=p^.rlink;

C．p^.llink^.rlink:=p^.llink; dispose(p); p^.llink^.rlink:=p^.rlink;

D．以上A，B，C 都不对。 

6. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN 是n，则pi 是( )。C

A. i B. n-i C. n-i+1 D. 不确定

7. 输入序列为ABC，可以变为CBA 时，经过的栈操作为（ ）B

A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop

C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop

8. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i 个栈( i =1,2)栈顶，栈1 的底在v[1]，栈2 的底在V[m]，则栈满的条件是（ ）。B

A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2]

9. 执行完下列语句段后，i 值为：（ ）B

int f(int x)

{ return ((x>0) ? x* f(x-1):2);}

int i ;

i =f(f(1));

A．2 B. 4 C. 8 D. 无限递归

10. 循环队列A[0..m-1]存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是( )。A

A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front

11. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。D

A. rear=rear+1 B. rear=(rear+1) mod (m-1)

C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)

12.若串S1=‘ABCDEFG’, S2=‘98’ ,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（ ）A

A．ABC###G1234 B．ABCD###2345 C．ABC###G2345 D．ABC###2345

13．若串S=’software’,其子串的数目是（ ）。B

A．8 B．37 C．36 D．9

14. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6 个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A 的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案： 2.1L 2.2J 2.3C 2.4I 2.5C

①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120G. 156 H. 234 I. 276 J. 282 K. 283 L. 288

⑤： A．行与列的上界相同 B. 行与列的下界相同

C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同

15. 已知广义表LS＝((a,b,c),(d,e,f)),运用head 和tail 函数取出LS 中原子e 的运算是( )。C

A. head(tail(LS)) B. tail(head(LS))

C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS))))

16. 下面说法不正确的是( )。A

A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表

C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构

二、判断题（1分×10）

1. 数据元素是数据的最小单位。( ) ×

2. 记录是数据处理的最小单位。 ( ) × 

3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ) ×

4．算法的优劣与算法描述语言无关，但与所用计算机有关。( ) ×

5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( ) ×

6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) ×

7. 取线性表的第i 个元素的时间同i 的大小有关. ( ) ×

8. 栈与队列是一种特殊操作的线性表。（ ）√

9. 一个稀疏矩阵Am*n 采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m 和n 的值互换，则就完成了Am*n 的转置运算。（ ）×

10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（ ）×

三、填空题（2分×20）

1．已知如下程序段

FOR i:= n DOWNTO 1 DO {语句1}

BEGIN

x:=x+1； {语句2}

FOR j:=n DOWNTO i DO {语句3}

y:=y+1; {语句4}

END；

语句1 执行的频度为 （1） ；语句2 执行的频度为 （2） ；语句3 执行的频度为 （3） ；语句4 执行的频度为 （4） 。9．（1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2。

2． 在双向循环链表中,向p 所指的结点之后插入指针f 所指的结点，其操作是_______、_______、_______、________。8．f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;

31. 下面是用c 语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L 返回逆置后的链表的头指针，试在空缺处填入适当的语句。

void reverse（linklist &L）{

p=null；q=L；

while（q！=null）

{ (1) ; q->next=p；p=q；(2)___ ; }

(3)_____;

}31. (1)L=L->next; ∥暂存后继(2)q=L; ∥待逆置结点(3)L=p; ∥头指针仍为L

3. 设有一个空栈， 栈顶指针为1000H( 十六进制) ， 现有输入序列为1 ， 2 ， 3 ， 4 ， 5 ， 经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4 个字节。    23 100CH

4. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1 空时，top[1]为_______，栈2 空时 ，top[2]为_______，栈满时为_______。 0 n+1 top[1]+1=top[2]

13．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回

0；

int f((1)________)

{int i=0,j=0;

while (s[j])(2)________;

for(j--; ireturn((3)_______)

} 13．（1）char s[ ] (2) j++ (3) i >= j

5. 已知广义表LS=(a，(b，c，d)，e),运用head 和tail 函数取出LS 中原子b 的运算是_______。28. head(head(tail(LS)))

四、应用题（5分×2）

1. 试述头结点,首元结点,头指针这三个概念的区别.

2. 试证明：若借助栈由输入序列1,2,…,n 得到输出序列为P1,P2,…,Pn（它是输入序列的一个排列），