一、选择题。(每小题2分，共40分)
(1) 计算机识别.存储和加工处理的对象被统称为____A____。
A.数据
B.数据元素
D.数据类型
C.数据结构
(2) 数据结构通常是研究数据的____ A _____及它们之间的联系。
A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑 (3) 不是数据的逻辑结构是____ A ______。
A.散列结构 B.线性结构 C.树结构 D.图结构
(4) 数据结构被形式地定义为
A.算法 B.数据元素 C.数据操作 D.逻辑结构 (5) 组成数据的基本单位是____ A ______。
A.数据项 B.数据类型 C.数据元素 D.数据变量
(6) 设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是____ A ______。
A.线性结构 B.树型结构 C.图型结构 D.集合
(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___ C ____。
A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构
(8) 在数据结构的讨论中把数据结构从逻辑上分为___ A ____。
A.内部结构与外部结构 B.静态结构与动态结构 C.线性结构与非线性结构 D.紧凑结构与非紧凑结构 (9) 对一个算法的评价，不包括如下____ B _____方面的内容。
A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度 (10) 算法分析的两个方面是__ A ____。
A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 (11) 线性表是具有n个___ C _____的有限序列（n≠0)。
A.表元素 B.字符 C.数据元素 D.数据项
(12) 线性表的存储结构是一种____ B ____的存储结构。
A.随机存取 B.顺序存取 C.索引存取 存取
(13) 在一个长度为n 的顺序表中，向第i个元素（1≤ i≤ n＋１）之前插入一个新元素时，需要向后移动____ B ____个元素。
+1
(14) 链表是一种采用____ B ____存储结构存储的线性表；
A.顺序 B.链式 C.星式 D.网状 (15) 下面关于线性表的叙述错误的是___ D _____。
A.线性表采用顺序存储必须占用一片连续的存储空间 B.线性表采用链式存储不必占用一片连续的存储空间 C.线性表采用链式存储便于插入和删除操作的实现 D.线性表采用顺序存储便于插入和删除操作的实现
(16) 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作序列为__ B ______。
A. s->next=p->next；p->next=-s； B. q->next=s； s->next=p； C. p->next=s->next；s->next=p； D. p->next=s；s->next=q；
(17) 设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为___ A _____。
A. p->next=p->next->next
B. p=p->next
C. p=p->next->next D. p->next=p (18) 下列说法哪个正确？____ D ______
A. 堆栈是在两端操作、先进后出的线性表 B. 堆栈是在一端操作、先进先出的线性表 C. 队列是在一端操作、先进先出的线性表 D. 队列是在两端操作、先进先出的线性表 (19) 栈和队列的共同点是 _____ C _______。
A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 (20) 栈与一般线性表的区别主要在_____D______。
A、元素个数 B、元素类型 C、逻辑结构 D、插入、删除元素的位置 (21) 链栈与顺序栈相比，比较明显的优点是_____D_____。
A、插入操作更加方便 B、删除操作更加方便 C、不会出现下溢的情况 D、不会出现上溢的情况 (22) 以下数据结构中哪一个是非线性结构___ D ______。
A.队列 B.栈 C.线性表 D.二叉树
(23) 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 _____ C ______。
A. i B. B. n=i C. n-i+1 D.不确定
(24) 当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行 ____ B ______语句修改top指针。
A. top++ B. top-- C. top=0 D. top
(25) 4个元素进S栈的顺序是A,B,C,D，经运算POP(S)后，栈顶元素是___ C _______。
A. A B. B C. C D. D
(26) 一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是____ C _____。
A. edcba B. decba C. dceab D. abcde
(27) 设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是____ C ______。
A. n-i B. n-1-i C. n+1-i D.不能确定
(28) 字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成___ B ___个不同的字符串？
A. 15 B. 14 C. 16 D. 21
(29) 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为____ D _______。
A. top=top+1; B. top=top-1; C. top->next=top; D. top=top->next;
(30) 设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是____ C _____。
A. 6 B. 4 C. 3 D. 2
(31) 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 ____ B _____。
A. 1和5 B. 2和4 C. 4和2 D. 5和1
(32) 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为____ C _____。
A. R-F B. F-R C. (R-F+M)%M D. (F-R+M)%M
(33) 设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为 ____ C _____。
A. front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； (34) 如下陈述中正确的是___ A ______。
A. 串是一种特殊的线性表 B. 串的长度必须大于零 C. 串中元素只能是字母 D. 空串就是空白串 (35) 下列关于串的叙述中，正确的是 ___ D ______。
A. 串长度是指串中不同字符的个数 B. 串是n个字母的有限序列 C. 如果两个串含有相同的字符，则它们相等
D. 只有当两个串的长度相等，并且各个对应位置的字符都相符时才相等 (36) 字符串的长度是指___ C ______。
A. 串中不同字符的个数 B. 串中不同字母的个数 C. 串中所含字符的个数 D. 串中不同数字的个数 (37) 两个字符串相等的充要条件是____ C ______。
A. 两个字符串的长度相等 B. 两个字符串中对应位置上的字符相等 C. 同时具备(A)和(B)两个条件 D. 以上答案都不对 (38) 串是一种特殊的线性表，其特殊性体现在____ B _______。
A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符
(39) 设有两个串p和q，求q在p中首次出现的位置的运算称作 ____ B ______。
A. 连接 B. 模式匹配 C. 求子串 D. 求串长
(40) 设串sI=\函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,1en(s2))，subs(sl,len(s2)，2))的结果串是__ D ___。
A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF (41) 函数substr(“DATASTRUCTURE”，5，9)的返回值为___ A ______。
A. “STRUCTURE” B. “DATA” C. “ASTRUCTUR” D. “DATASTRUCTURE” (42) 设串S=”I AM A TEACHER!”，其长度是____ D ______。
A. 16 B. 11 C. 14 D. 15
(43) 假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为____B____。
A. 15 B. 16 C. 17 D. 47 (44) 假定一棵二叉树的结点数为18个，则它的最小高度____B____。
A. 4 B. 5 C. 6 D. 18 (45) 在一棵二叉树中第五层上的结点数最多为____C____。
A. 8 B. 15 C. 16 D. 32 (46) 在一棵具有五层的满二叉树中，结点总数为____A____。
A. 31 B. 32 C. 33 D. 16
(47) 已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为____B____。
A. 1 B. 2 C. D. 4
(48) 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为____C____。
A. 23 B. 37 C. 44 D. 46
(49) 在树中除根结点外，其余结点分成m (m≥0)个____A ____的集合T1,T2,T3...Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1≤i≤m)。
A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交
(50) 如果结点A有三个兄弟，而且B是A的双亲，则B的出度是____B____。
A. 3 B. 4 C. 5 D. 1
(51) 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____B____倍。
A. 1/2 B. 1 C. 2 D. 4 (52) 具有n个顶点的无向完全图，边的总数为____ D____条。
A. n-1 B. n C. n+1 D. n*(n-1)/2
(53) 在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于____C ____。
A. i+j B. i-j C. 1 D. 0
(54) 图的深度优先或广度优先遍历的空间复杂性均为____A____ 。(访问标志位数组空间)
A. O(n) B. O(e) C. O(n-e) D. O(n+e)
(55) 请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用折半法查找关键码12需做____ C ___次关键码比较。
(56) 对线性表进行折半查找时，必须要求线性表 ____ C ____。
A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键字有序排列 D. 以链接方式存储，且结点按关键字有序排列
(57) 设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为___ B _____。
A. O(1) B. O(log2n) C. O(n) D. O(n)
(58) 依次插入序列(50，72，43，85，75，20，35，45，65，30)后建立的二叉搜索树中，查找元素35要进行__ A ___元素间的比较。
次
次
次
次
2
(59) 设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择___ B _____。
A. 小于等于m的最大奇数 C. 小于等于m的最大偶数
B. 小于等于m的最大素数 D. 小于等于m的最大合数
(60) ____ D _____是HASH查找的冲突处理方法。
A.求余法 B. 平方取中法 C. 二分法 D. 开放地址法
(61) 当α的值较小时，散列存储通常比其他存储方式具有_____ B ______的查找速度。
A. 较慢
B. 较快
C. 相同 D. 不确定
(62) 对线性表进行折半查找最方便的存储结构是____ B _______。
A．顺序表 B．有序的顺序表 C．链表 D．有序的链表
(63) 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用_____ D ____查找方法。
A．分块 B．顺序 C．折半 D．散列
(64) 散列函数有一个共同性质，即函数值应按___ C ______取其值域的每一个值。
A．最大概率 B．最小概率 C．同等概率 D．平均概率 (65) 下述排序算法中，稳定的是___ B _____。
A.直接选择排序 B. 直接插入排序 C.快速排序 D.堆排序 (66) 下列排序算法中，____ A ____需要的辅助存储空间最大。
A.快速排序
B.插入排序
C.希尔排序
2
D.基数排序
(67) 下列各种排序算法中平均时间复杂度为O(n)是___ D _____。