华中师范大学网络学院《数据结构》试题库及答案.docx
《华中师范大学网络学院《数据结构》试题库及答案.docx》由会员分享，可在线阅读，更多相关《华中师范大学网络学院《数据结构》试题库及答案.docx（92页珍藏版）》请在冰点文库上搜索。
华中师范大学网络学院《数据结构》试题库及答案
华中师范大学网络学院《数据结构》试题库及答案
一、选择题
1在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构
C．线性结构和非线性结构D．内部结构和非内部结构
2．算法分析的目的是（ ）；
Ａ.找出数据结构的合理性 B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进 D.分析算法的易懂性和文档性
3.算法分析的两个主要方面是（ ）。
A.空间复杂度和时间复杂度 B.正确性和简单性
C．可读性和文档性 D.数据复杂性和程序复杂性
4．一个顺序表（即顺序存储的线性表）第一个元素的存储地址是100，每个元素的长度为2，
则第5个元素的地址是（）。
A．100B．108C．100D．120
5．在一个长度为n的顺序表中，向第i个元素（1≤i≤n＋１）之前插入一个新元素时，
需要向后移动（）个元素。
A.n-i B.n-i-1 C.n-i+1 D.i
6．从一个长度为n的顺序表中删除第i个元素（1≤i≤n＋１）时，需要向前移动（）
个元素。
A.n-i B.n-i-1 C.n-i-1 D.i
7．若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个元素的算法的时间
复杂度是（ ）
Ａ.O（n） B.O（n*n） C.O（nlog2n） D.O（log2n）
8．线性表的存储结构是一种（）的存储结构
A．随机存取B．顺序存取C．索引存取D．HASH存取
9.线性表的链式存储结构是一种（）的存储结构。
A．随机存取B．顺序存取C．索引存取D．HASH存取
10．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100,则第12个元素的存储地址是（）
A．112 B.144 C.148 D.412
11．若频繁地对线性表进行插入和删除操作，该线性表应该采用（ ）存储结构。
A．散列 B.顺序 C.链式 D.任意
12．线性表若采用链表存储结构时，要求内存中可用存储单元的地址（）。
A．必须是连续的B．部分地址必须是连续的
C．一定是不边疆的D．连续不连续都可以
13．在非空线性链表中，在由p所指的链结点后面插入一个由q所指的链结点的过程是依次
执行（）
A．q->next=p; p->next=q;
B．q->next=p->next;p->next=q;
C．q->next=p->next;p=q;
D．p->next=q;q->next=p;
14．若删除非空线性链表中由p所指链结点的直接后继结点的过程是依次执行（）
A．r=p->next;p->next=r; callRET（r）
B．r=p->next;p->next=r->next;callRET（r）
C．r=p->next;p->next=r->next;callRET（p）
D．p->next=p->next->next; callRET（p）
15．删除一个双链表中结点p（非头结点和尾结点）的操作是（）.
A.p->left->right=p->left;p->right->left=p->right
B.p->left->right=p->right;p->right->left=p->ieft
C.p->left=NULL;p->right=NULL
D.p->right->left=p;p->left->right=p
16．在一个双链表中结点p之后插入一个结点s的操作是（）。
A.s->right=p;s->left=p->right;p->right->left=s;p->right=s
B.s->right=p->right;p->right->left=s;s->right=p;p->left=s
C.s->right=p->right;s->left=p;p->left->left=s;p->right=s
D.s->right=p;p->left->left=s;p->right=s;s->right=p->right
17．非空的循环单链表head的尾结点（由p所指向）满足（）。
A.p->next=NULL; B.p=NULL;
C.p->next=head; D.p=head;
18．在循环双链表的p所指结点之后插入s的操作是（）。
A.p->right=s;s->left=p;p->right->left=s;s->rigth=p->right;
B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;
C.s->left=p;s->right=p->right;p->right->left=s;
D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;
19．设单链表中结点的结构为（data,link）．已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?
（）
A.s->link=p->link;p->link=s;B.q->link=s;s->link=p;
C.p->link=s->link;s->link=p;D.p->link=s;s->link=q;
20．设单链表中结点的结构为（data,link）.已知指针p所指结点不是尾结点,若在*p之后插入结点*s,则应执行下列哪一个操作?
（）
A.s->link＝p; p->link=s;B.s->link=P->link; P->link=s;
C.s->link＝p->link; p=s;D.p->link=s; s->link=p;
21． 设单链表中结点结构为（data,link）.若想摘除结点*p的直接后继,则应执行下列哪个操作?
（）
A.p->link=p->link-.link;B.p=p->link=p->link->link;
C.p->link=p->link;D.p=p->link->link;
22．设单循环链表中结点的结构为（date，link）且rear是指向非空的带表头结点的单循环链表的尾结点指针。
若想删除链表的第一个结点,则应执行下列哪一个操作?
（）
A.s=rear;rear=rear->link;deletes;B.rear=rear->link;deleterear;
C.rear=rear->link->link;deleterear;D.s=rear->link->link;rear->link->link=s->link;deletes;
23． 设双向循环链表中结点的结构为（data，1Link，rLink），且不带裹头结点．若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作?
（）
A.p->rLink＝s;s->1Link＝p;p->rLink一-1Link＝s;s->rLink=p->rLink;
B.p->rLink＝s;p->rLink->1Link＝s;s->1Link＝p;s->rLink＝P->rLink，
C.s->1Link＝P;s->rLink＝p->rlink;P->rLink=s;p->rlink->lLink=s;
D.s->1Link＝P;s->rLink＝p->rLink;P->rLink->1Link＝s;p->rLink＝s;
24．数组通常具有的两种基本操作是（）。
A．建立与删除 B．索引和修改
C．查找和修改 D．查找与索引
25．二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从
0到8，列下标j的范围从1到10，则存放M至少需要（）个字节
A．90 B．180 C．240 D．540
26．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5,M按行存储时元素M[3Ⅱ5]的起始地址与M按列存储时元素（）的起始地址相同。
A．M[2][4] B．M13][4] C．M[3][5] D．M14][4]
27．数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从
首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（）。
A．80 B．100 C．240 D．270
28．数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（）。
A．SA+141 B．SA+144 C．SA+222 D．SA+225
29．数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从
首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5]18]的起始地址为（）。
A．SA+141 B．SA+180 C．SA+222 D．SA+225
30．下面的说法中，不正确的是（）。
A．数组是一种线性表结构
B．数组是一种定长的线性表结构，
C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等
D．数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作
31．设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1..n（n-1）／2]中，对任一下三角部分元素ai,j（i），在一组数组B的下标位置k的值是（）。
A．i（i-1）／2+j-1 B．i（i-1）／2+j
C．i（i+1）／2+j-1 D．i（i+1）／2+i
32．下面的说法中，不正确的是（）。
A．只须存放对称矩阵中包括主对角线元素在内的下（或上）三角部分的元素即可
B．只须存放对角矩阵中的非零元素即可
C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储
D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储
33．对一些特殊矩阵采用压缩存储的目的主要是为了（）。
A．表达变得简单
B．对矩阵元素的存取变得简单
C．去掉矩阵中的多余元素
D．减少不必要的存储空间的开销
34．若将n阶对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，则该对称矩阵在B中占用了（）个数组元素。
A．n/2 B．n*（n-1）C．n*（n+1）／2 D．n*（n-1）
35．若将对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，那么，A中某元素ai（i<0）在B中的位置是（）。
A．（i*（i-1））／2+j B．（i*（i-1））／2-j
C．（j*（j-1））／2+i D．（j*（j-1））/2-i
36．稀疏矩阵一般的压缩存储方法有两种，即（）。
A．二维数组和三维数组 B．三元组和散列
C.三元组和十字链表 D．散列和十字链表
37.串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储 B．数据元素是一个字符
c．可以链接存储 D．数据元素可以是多个字符
38.串是（）。
A．不少于一个字母的序列 B．任意个字母的序列
C．不少于一个字符的序列 D．任意个字符的序列
39.串的长度是（）。
A．串中不同字母的个数
B．串中不同字符的个数
c．串中所含字符的个数，且大于0
D．串中所含字符的个数
40.设有两个串p和q，求q在p中首次出现的位置的运算称作（）。
A．连接 B．模式匹配 C．求子串 D．求串长
41.设串s="ABUBG",len（s）返回串s的长度，则len（s）是（）。
A．2 B．4 C．5 D．6
42.设串s="ABCDEFG",subs（s，U）返回串s的从序号i的字符开始的j个字符组成的子串，则
subs（s,3,3）的结果串是（）。
A．ABC B．CDE C．DEF D．EFG
43.设串sI="ABCDEFG",s2="PQRST",函数con（x,y）返回x和y串的连接串,subs（s，山）返回串s的从序号i的字符开始的j个字符组成的子串，len（s）返回串s的长度，则con（subs（s1,2,1en（s2）），subs（sl,len（s2），2））的结果串是（）。
A．BCDEF B．BCDEFG C．BCPQRST n。
BCDEFEF
44.下列关于串的叙述中，正确的是（）。
A．串长度是指串中不同字符的个数
B．串是n个字母的有限序列（nj0）
c．如果两个串含有相同的字符，则它们相等
45． 栈和队列的共同点是（）。
A．都是先进后出
B．都是先进先出
C．只允许在端点处插入和删除元素
D．没有共同点
46． 判定一个栈ST（最多元素为m0）为空的条件是（ ）。
A．ST—>t!
=0 B．ST—>t==0
C．ST—>t!
=m0 D．ST—>t==m0
47．判定一个栈ST（最多元素为m0）为栈满的条件是（ ）。
A．ST—>top!
=0 B．ST—>top==0
C．ST—>top!
=m0 D．ST—>top==m0
48． 一个栈的人栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）。
A．edcba B．decba C．dceab D．abcde
49． 一个栈的人栈序列是l，2，3，4，则栈的可能的输出序列是（ ）。
A．1，4，2，3 B．2，1，4，3 C。
4，2，1，3 D．4，2，3，l
50．若己知一个栈的人栈序列是1，2，3，…,n，其输出序列为p1,p2,p3,…,pn，若p1则pi为（）
A．i B．n=i C．n-i+1 D．不确定
51.若堆栈采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶指针top的变化是（）。
A.不变B.top0C.toptop-1D.toptop+1
52．向一个栈顶指针为HS的链栈中插入—个s所指结点时，则执行（）
A．HS->next=S； B．S->next=HS->next；HS->next=S；
C．S->next=HS；HS=S； D．S->next=HS；HS=HS->next；
53．从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。
A．X=HS；HS=HS->next； B．X=HS->data；
C．HS=HS->next；K=HS->data； D．x=HS->data；HS=HS->next
54．中缀表达式A-（B+C／D）*E的后缀形式是（）。
A．ABC+D／*E- B．ABCD／+E*-
C．AB-C+D／E* D．ABC-+D/E*
55.若堆栈采用链式存储结构，栈顶指针为top，向堆栈插入一个数据信息为item的新元素的过程式依次执行：
callGETNODE（p）,data（p）item,（）,topp.
A.ptopB.toppC.link（p）topD.link（top）p
56．若某堆栈的输入序列为1，2，3，…，n-1，n，输出序列的第1个元素为n，则第i个输出元素为（）。
A.n-i+l B．n-i C．i D．哪个元素无所谓
57．一个队列的人列序列是1，2，3，4，则队列的输出序列是（ ）。
A．4，3，2，1 B．1，2，3，4 C。
1，4，3，2 D．3，2，4，l
58．判定一个队列QU（最多元素为m0）为空的条件是（ ）。
A．QU—>rear-QU—>front==m0 B．QU—>rear—QU—>front—1==m0
C．QU—>front==QU—>rear D．QU—>front==QU—>rear+l
59．判定一个队列QU（最多元素为m0）为满队列的条件是（ ）。
A．QU->rear-QU->front==mO B．QU->rear-QU->front-1==m0
C．QU->front==QU->rear D．QU->front==QU->rear+l
60．判定一个循环队列QU（最多元素为m0）为空的条件是（）。
A．QU->front==QU->rear B．QU->front!
=QU->rear
C．QU->front=（QU->rear+1）％m0 D．QU->front!
=（QU->rear+1）％m0
61．判定一个循环队列QU（最多元素为m0）为满队列的条件是（）
A．QU->front==QU->rear B．QU->front!
=QU->rear
C．QU->front==（QU->rear+1）％m0 D．QU->front!
=（QU->rear+1）％m0
62．表达式a*（b+c）-d的中缀表达式是（）
A.abcd*+- B．abc+*dC．abc*+d- D．-+*abcd
63．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓冲区应该是一个（）结构。
A．线性表 B．数组 C．堆栈 D．队列
64．设计一个递归问题的非递归算法通常需要设置（）结构。
A．线性表 B．数组 C．堆栈 D．队列
65.队列是限定在（ ）处进行插入操作的线性表
A.任意端点 B.队头
C.队尾 D.中间
66.队列是限定在（ ）处进行删除操作的线性表
A.任意端点 B.队头
C.队尾 D.中间
67.队列中元素的个数是（ ）
A.不变的 B.可变的
C.任意的 D.0
68．递归函数f（n）=f（n-1）十n（n>1）的递归出口是（）。
A．f
（1）=0 B．f
（1）=1C．f（0）=1 D．f（n）=n
69．广义表中元素分为（）
A．原子元素 B.表元素
C．原子元素 D.任意元素
70．广义表的长度是指（ ）
A，广义表中元素的个数 B。
广义表中原子元素的个数
C．广义表中表元素的个数 D．广义表中括号嵌套的层数
71.广义表的深度是指 （ ）
A．广义表中元素的个数 B．广义表中原子元素甜个数
C.广义表中表元素的个数 D．广义表中括号嵌套的层数
72．广义表A：
<<），（a）， A．2 B．3 C．4 D．5
73．广义表A=（（），（a），（b，（c，d）））的深度为（）
A．2 B．3 C．4 D．5
74.树最适合用来表示（）。
A．有序数据元素
B．无序数据元素
C.元素之间具有分支层次关系的数据
D．元素之间无联系的数据
75.有64个结点的完全二叉树的深度为（树根的层次为1）（）
A．8 B．7 C．6 D．
76.在一棵树中，若结点A有3个兄弟，结点B是结点A的双亲结点，那么结点B的度为（）。
A．3 B．1 C．4 D．5
77.如图17．2所示的t2是由有序树t1转换而来的二叉树，那么树t1有（）个叶结点。
A．4 B．5 C．6 D．7
78.在m叉树中，度为0的结点称为（）。
A．兄弟 B．树叶 C．树根 D．分支结点
79．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）次序的遍历实现编号。
A．前序 B．中序 C．后序 D.从根开始的层次遍历
80．某非空二叉树的前序序列和后序序列正
升级会员 