1. 从逻辑上可以把数据结构分为（ C ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构2. 在下面的程序段中，对x的赋值语句的频度为（ C ）。

For（k=1；k<=n；k++）For（j=1；j<=n；j++）x=x＋1；n)A．O(2n) B．O(n) C．O(n2) D．O(log23. 采用顺序存储结构表示数据时，相邻的数据元素的存储地址（ A ）。

A．一定连续 B．一定不连续C．不一定连续 D．部分连续、部分不连续4. 下面关于算法的说法，正确的是（ D ）。

A．算法的时间复杂度一般与算法的空间复杂度成正比B．解决某问题的算法可能有多种，但肯定采用相同的数据结构C．算法的可行性是指算法的指令不能有二义性D．同一个算法，实现语言的级别越高，执行效率就越低5. 在发生非法操作时，算法能够作出适当处理的特性称为（ B ）。

A．正确性 B．健壮性 C．可读性 D．可移植性第二章线性表1. 线性表是（ A ）。

A．一个有限序列，可以为空 B．一个有限序列，不能为空C．一个无限序列，可以为空 D．一个无限序列，不能为空2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（ A ）个元素。

A．n/2 B．（n＋1）/2 C．（n－1）/2 D．n3．线性表采用链式存储时，其地址（ D ）。

A．必须是连续的 B．部分地址必须是连续的C．一定是不连续的 D．连续与否均可以4．用链表表示线性表的优点是（ C ）。

A．便于随机存取 B．花费的存储空间较顺序存储少C．便于插入和删除 D．数据元素的物理顺序与逻辑顺序相同5．链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ C ）存储方式最节省运算时间。

A．单链表 B．双链表 C．单循环链表 D．带头结点的双向循环链表6．下面关于线性表的叙述，错误的是（ B ）。

A．线性表采用顺序存储，必须占用一片地址连续的单元B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链式存储，不必占用一片地址连续的单元D．线性表采用链式存储，不便于进行插入和删除操作7．单链表中，增加一个头结点的目的是为了（ C ）。

A．使单链表至少有一个结点 B．标识表结点中首结点的位置C．方便运算的实现 D．说明单链表是线性表的链式存储8．在单链表指针为p的结点之后插入指针为s结点，正确的操作是（ B ）。

A．p->next=s；s->next=p->next；B．s->next=p->next；p->next=s；C．p->next=s；p->next=s->next；D．p->next=s->next；p->next=s；9．在双向链表存储结构中，删除p所指的结点时须修改指针（ A ）。

A．（p-> prior)-> next = p->next ; （p->next）->prior =p-> prior ;B．p-> prior=（p-> prior）-> prior ; （p-> prior）-> next =p ;C．（p->next）->prior =p ; p->rlink=（p-> next）-> next ;D．p->next =（p-> prior）-> prior ; p-> prior =（p-> next）-> next10. 完成在双向循环链表结点p之后插入s的操作是（ D ）。

A．p->next =s; s-> prior =p; p-> next-> prior =s; s-> next =p-> next;B．p->next-> prior =s; p-> next =s; s-> prior =p; s-> next =p-> next;C．s-> prior =p; s-> next = p->next; p-> next =s; p-> next-> prior =s;D．s-> prior =p; s-> next = p->next; p-> next-> prior =s;p-> next =s;11. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ B ）存储方式最节省运算时间。

A．单链表 B．顺序表 C．双向链表 D．单循环链表12. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表C．双向链表 D．仅有尾指针的单循环链表第三章栈和队列1．向一个栈顶指针为top的链栈中插入一个p所指结点时，其操作步骤为（ C ）。

A．top->next=p； B．p->next=top->next；top->next=p；C．p->next=top；top=p； D．p->next=top；top=top->next；2．对于栈操作数据的原则是（ B ）。

A．先进先出 B．后进先出C．后进后出 D．不分顺序3．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p n 是n，则Pi为（ D ）。

A．i B．n－i C．n－i＋l D．不确定4．表达式a *（b－c）＋d的后缀表达式是（ B ）。

A．abcd*－＋ B．abc－*d＋C．abc*－d＋ D．＋－*abcd5．采用顺序存储的两个栈的共享空间S[1..m]，用top[i]代表第i个栈（i=1，2）的栈顶，栈1的底在S[1]，栈2的底在S[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]6．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ C ）。

A．edcba B．decba C．dceab D．abcde7．在一个链队列中，若f、r分别为队首、队尾指针，则插入p所指结点的操作为（ B ）。

A．f->next=p；f=p B．r->next=p；r=pC．p->next=r；r=p D．p->next=f；f=p8．用不带头结点的单链表存储队列时，在进行删除运算时（ D ）。

A．仅修改头指针 B．仅修改尾指针C．头、尾指针都要修改 D．头、尾指针可能都要修改9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。

A．队列 B．静态链表 C．栈 D．顺序表10. 栈和队都是（ C ）。

A．顺序存储的线性结构 B．链式存储的非线性结构C．限制存取点的线性结构 D．限制存取点的非线性结构第四章字符串及线性结构的扩展1. 下面关于串的叙述，错误的是（ C ）。

A．串是字符的有限序列B．串既可以采用顺序存储，也可以采用链式存储C．空串是由空格构成的串D．模式匹配是串的一种重要运算2. 串的长度是指（ B ）。

A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数3.4. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（1）（ D ）个字节；M的第8列和第5行共占（2）（ A ）个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的（3）（ C ）元素的起始地址一致。

（1）A. 90 B. 180 C. 240 D. 540（2）A. 108 B. 114 C. 54 D. 60（3）A. M[8][5] B. M[3][10] C. M[5][8] D. M[0][9]5. 数组A中，每个元素的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（1）（ C ）；若该数组按行存放，元素A[8][5]的起始地址为（2）（ D ）；若该数组按列存放，元素A[8][5]的起始地址为（3）（ B ）。

（1）A. 80 B. 100 C.240 D. 270（2）A. SA+141 B. SA+144 C. SA+222 D. SA+225（3）A. SA+141 B. SA+180 C. SA+117 D. SA+2256. 稀疏矩阵采用压缩存储，一般有（ C ）两种方法。

A．二维数组和三维数组 B．三元组和散列C．三元组表和十字链表 D．散列和十字链表第五章树结构1. 下列说法正确的是（ C ）。

A．二叉树中任何一个结点的度都为2 B．二叉树的度为2C．一棵二叉树的度可小于2 D．任何一棵二叉树中至少有一个结点的度为22. 以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n＞0），空链域的个数为（ C ）。

A．2n－1 B．n－1 C．n＋l D．2n＋l3. 线索化二叉树中，某结点*p没有孩子的充要条件是（ B ）。

A. p->lchild=NULLB. p->ltag=1且p->rtag=1C. p->ltag=0D. p->lchild=NULL且p->ltag=14. 如果结点A有3个兄弟，而且B是A的双亲，则B的度是（ B ）。

A．3 B．4 C．5 D．15. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1，2，…，n，且有如下性质：T中任意结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于v左子树上结点的最大编号加1，这是按（ B ）编号的。

A. 中序遍历序列B. 先序遍历序列C. 后序遍历序列D. 层次顺序6. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有（ C ）个。

A．n－1 B．n C．n＋l D．n＋27. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ C ）。

A．500 B．501 C．490 D．4958. 设森林F中有3棵树，第1、第2和第3棵树的结点个数分别为N1，N2和N3。