数据结构考试试题(带答案)
××科技大学成都学院二零零八至二零零九学年第一学期
数据结构课堂测试（60分钟）闭卷考试时间：
题号一二三总分评卷教师
分数
一．填空题（每空2分，共40分）；
1.数据结构算法中，通常用时间复杂度和__空间复杂度___两种方法衡量其效率。
2.下面程序段的时间复杂度为___O(n2)______。(n>1)
for(i = 1; i <= n; i++)
for(j = 1; j <= i; j++)
x = x + 1;
3.静态链表中指针表示的是______下一结点的地址______。
4.线型表、栈和队列都是____线型_______结构，可以在线型表的____任意___位置
插入和删除元素；对于栈只能在____栈顶_____插入和删除元素；对于队列只能在____队尾___插入元素和_____队头_____删除元素。
5.在具有n个单元的循环队列中，队满时共有_____n-1____个元素。
6.在一个长度为n 的顺序表中第i 个元素（1<=i<=n）之前插入一个元素时，需向
后移动__n-i+1__个元素。
7.在n个结点的单链表中要删除已知结点*p，需找到它的_____前驱________。
8.带有一个头结点的单链表head为空的条件是_________head->next=
=NULL__________。
9.在栈顶指针为hs的链栈中，判断栈空的条件是_________hs= =NULL__________。
10.在hq的链队列中，判定只有一个结点的条件是
__hq.front->next==hq.rear________。
11.非空的循环单链表head的尾结点（由p指向），满足条件____p->next==head。
12.两个串相等的充分必要条件是______串长相等且对应字符相等_______。
13.空串是_______长度为0的串______，其长度等于___0________。
14.空格串是______由空格字符组成的串______，其长度等于_____空格的个数
_________ 。
二．单项选择题（每题2分，共30分）；（说明：请将答案填入下表中）题号 1 2 3 4 5 6 7 8 9 10
答案 A A B B D B C B B C
题号11 12 13 14 15
答案 A A C D D
1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运
算，则利用（A）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表2.设a1、a2、a3为3个结点，则如下的链式存储结构称为：A
表元编号结点表元间关系
1 a1 3
2 a2 1
3 a3 2
A．循环链表 B．单链表 C．双向循环链表 D．双向链表
3.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？
（B ）
A. 5 4 3 6 1 2
B. 3 4 6 5 2 1
C. 4 5 3 1 2 6
D. 2 3 4 1 5
6
4.若栈采用顺序存储方式存储，现两栈共享空间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]
5.数组Ｑ［ｎ］用来表示一个循环队列，front为当前队列头元素的前一位置，rear
为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为(D)
A. rear－front
B.（n＋front－rear）% n
C. n＋rear－front
D.（n＋rear－front）% n
6.设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4,e5 和e6 依次通过栈S，
一个元素出栈后即进队列Q，若6 个元素出队的序列是e2，e4,e6,e5，e3,e1 则栈S 的容量至少应该是( B)。
A． 6 B. 4 C. 3 D. 2
7.在数据结构中，从逻辑上可以把数据结构分成（C）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构
C．线性结构和非线性结构 D．内部结构和外部结构
8.判定一个顺序栈ST（最多元素为N）为空的条件是（B ）。
A．ST．top ！= ST.base B．ST．top==ST.base
C．ST．top！=N D．ST．top==N
9.一个队列的入列序列是1，2，3，4，则队列的输出序列是 B 。
A．4,3,2,1 B．1,2,3,4 C．1,4,3,2 D．3,2,4,1
10.判定一个循环队列QU(最多元素为N)为空的条件是 C 。
A．QU.front== （QU.rear+1）%N B．QU.front！= （QU.rear+1）%N
C．QU.front== QU.rear D．QU.front！= QU.rear
11.判定一个循环队列QU（最多元素为m0）为满队列的条件是 A 。
A．QU.front== （QU.rear+1）%N B．QU.front！= （QU.rear+1）%N
C．QU.front== QU.rear D．QU.front！= QU.rear+1
12.不带头结点的单链表head为空的判定条件是 A
A．head=NULL B．head - >next=NULL C．head- >next=head
D．head!=NULL
13.15.在双向链表指针p 的结点前插入一个指针q 的结点操作是（C ）。
A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;
C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
14.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，
需平均比较___D___个结点。
A．n B．n/2 C．(n—1)/2 D．(n+1)/2 15.设串s1=‘ABCDEFG’,s2='PQRST',函数con(x,y)返回x和y串的连接串，subs
（s,i,j）返回串s的从序号i的字符开始的j个字符组成的字串， len(s)返回串s的长度，则con(subs(s1,2,len(s2)), subs(s1,len(s2),2))的结果串是 D A）BCDEF B）BCDEFG C）BCPQRST D）BCDEFEF
三．综合题（每题6分，共30分）
1.线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线
性表L={23，17，47，05，31}，若它以单链表方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节,由大写字母表示）组成，如下所示：
100120
17
31t
p
05s
47q
23r
其中指针p，q，r，s，t的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？(共6分)
2.答：p= 108 q = 116 r = 112 s= 0 或
NULL
t= 100 首址= 104 末址= 112 。
3.如果想将输入的一个字符序列逆序输出，如输入“abcdef ”，输出“fedcba”，请
分析用线性表、堆栈和队列等方式正确输出的可能性？(共6分)
线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；
堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；
队列是先进先出，不易实现。
4.写出删除顺序表中第i个元素的算法：(共6分)
Status ListDelete_sq(SqList &L, int i, ElemType &e) Status del_sqllist(SqList &L,int i, ElemType &e) {
if (i < 1‖i > L.length) return ERROR;
e= L.elem[i];
for (j=i+1;j<= L.length;j++)
L.elem[j-1]= L.elem[j];
--L.length;
return OK;
}
5.写出顺序栈的入栈算法(共6分)
Status Push(SqStack &S, SelemType e)
void Push ( Stack &S, ElemType e )
{ //在栈顶之上插入元素e为新的栈顶元素
p = new LNode ; // 建新的结点
if(!p) exit(1) ; // 存储分配失败
p -> data = e;
p->next=S.top ;// 链接到原来的栈顶
S.top = p; // 移动栈顶指针
++S.length;// 栈的长度增1
} // Push
6.写出链队列的出队列算法(共6分)
Status DeQueue(LinkQueue &Q, QelemType &e)
Status DeQueue (LinkQueue &Q, QElemType &e) {
// 若队列不空，则删除Q的队头元素，
//用e 返回其值，并返回OK；否则返回ERROR
if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data;
Q.front->next = p->next;
if (Q.rear == p) Q.rear = Q.front;
free (p); return OK;
}
××科技大学成都学院
2008~2009学年第一学期中期试题——数据结构答案
一．填空题（每题2分，共40分）；
题号参考答案
1 空间复杂度
2 O(n2)
3 下一结点的地址
4 线型，任意，栈顶，队尾，队头
5 n-1
6 n-i+1
7 前驱
8 head->next= =NULL
9 hs= =NULL
10 hq.front->next==hq.rear
11 p->next==head
12 串长相等且对应字符相等
13 长度为0的串，0
14 由空格字符组成的串，空格的个数
二．单项选择题（每题2分，共30分）；
题号 1 2 3 4 5 6 7 8 9 10
答案 A A B B D B C B B C
题号11 12 13 14 15
答案 A A C D D
三．综合题（共30分）
7.p= 108 q = 116 r = 112 s= 0 或NULL
t= 100 首址= 104 末址= 112 。
8.线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；
堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；
队列是先进先出，不易实现。
3．Status del_sqllist(SqList &L,int i, ElemType &e)
{
if (i < 1‖i > L.length) return ERROR;
e= L.elem[i];
for (j=i+1;j<= L.length;j++)
L.elem[j-1]= L.elem[j];
--L.length;
return OK;
}
4.
void Push ( Stack &S, ElemType e )
{ //在栈顶之上插入元素e为新的栈顶元素
p = new LNode ; // 建新的结点
if(!p) exit(1) ; // 存储分配失败
p -> data = e;
p->next=S.top ;// 链接到原来的栈顶
S.top = p; // 移动栈顶指针
++S.length;// 栈的长度增1
} // Push
5．Status DeQueue (LinkQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素，
//用e 返回其值，并返回OK；否则返回ERROR
if (Q.front == Q.rear) return ERROR;
p = Q.front->next; e = p->data;
Q.front->next = p->next;
if (Q.rear == p) Q.rear = Q.front;
free (p); return OK;
}
全真模拟试题（一）
一、单项选择题（在每小题的4个备选答案中，选出正确的答案，并将其号码填在
题干的括号内。每小题2分，共24分）
1．若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ 4 ）存储方式最节省时间。
①单链表②双链表③单向循环④顺序表
2．串是任意有限个（ 1 ）
①符号构成的序列②符号构成的集合
③字符构成的序列④字符构成的集合
3．设矩阵A（a ij，l≤i,j≤ 10）的元素满足：
a ij≠0(i≥j, l≤i, j≤ 10)
a ij=0 (i 现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为 ①2340 ②2336 ③2164 ④2160 4．如果以链表作为栈的存储结构，则退栈操作时（） ①必须判别栈是否满 ②对栈不作任何判别 ③必须判别栈是否空 ④判别栈元素的类型 5．设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（） ①front=front+1 ②front=(front+1)% m ③rear=(rear+1)%m ④front=(front+1)%(m+1) 6．深度为6（根的层次为1）的二叉树至多有（）结点。 ① 64 ②32 ③31 ④63 7．将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（） ①24 ②25 ③23 ④无法确定 8．设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（） ①G’为G 的子图②G’为G 的边通分量 ③G’为G的极小连通子图且V’=V④G’为G的一个无环子图 9．用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（）①一定都是同义词②一定都不是同义词 ③都相同④不一定都是同义词 10．二分查找要求被查找的表是（ 3 ） ①键值有序的链接表②链接表但键值不一定有序 ③键值有序的顺序表④顺序表但键值不一定有序 11．当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（） ①n2 ②nlog2n ③log2n ④n-1 12．堆是一个键值序列{k1,k2,…, k n},对i=1,2,…,|_n/2_|,满足( ) ①k i≤k2i≤k2i+1②k i ③k i≤k2i且k i≤k2i+1(2i+1≤n)④k i≤k2i或k i≤k2i+1(2i+1≤n) 二、判断题（判断下列各题是否正确，正确在括号内打“V”，错的找“X”。每小题1分，共10分） 1．双链表中至多只有一个结点的后继指针为空。（） 2．在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（） 3．对链表进行插入和删除操作时，不必移动结点。（） 4．栈可以作为实现程序设计语言过程调用时的一种数据结构。（） 5．在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧 6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( ) 7．“顺序查找法”是指在顺序表上进行查找的方法。（） 8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（） 9．键值序列{A，C，D，E，F，E，F}是一个堆。 10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（） 三、填空题（每空2分，共24分） 1．设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___________；r=s; r->next=null;。 2．在单链表中，指针p 所指结点为最后一个结点的条件是___________。 3．设一个链栈的栈顶指针是ls，栈中结点格式为info | link ,栈空的条件是__________.如果栈不为空，则退栈操作为p=ls；___________；free(p);。 4．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有____________ 个叶子的结点。 5．树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和_________________ . 6． N个顶点的连通图的生成树有___________条边。 7．一个有向图G中若有弧 8．设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行（按递增排序），最省时间，最费时间。9．下面是将键值为x 的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。 typedef struct pnode {int key; struct pnode *le ft, *right; }pnode; void searchinsert(int x, pnode t ) /*t为二叉排序树根结点的指针*／ {if ( ) {p=malloc(size); p->key=x;p->lchild=null; p->rchild=null;t=p; } else if (x else_________; } 四、应用题（本题共２８分） 1．树的后根遍历方法是：若树非空则（４分） （1）依据次后根遍历根的各个子树Ｔ １，Ｔ ２ ，……Ｔm; （2）访问根结点 2. 将下图的森林转换为二叉树。（４分） 3. 下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。（４分） 图7.11 遍历无向图(a) 无向图G6 (b) 深度优先搜索示例 (c) G6的邻接表表示(c) 表头结点 4．已知一个无向图的邻接表如下图所示。（本题４分，每小题２分） (1) 画出这个图。 (2) 以v1为出发点，对图进行广度优先搜索，写出所有可能的访问序列。 5.设n个元素的有序表为Ｒ，Ｋ为一个给定的值，二分查找算法如下： int binsearch(sqlist R, keytype K) {j=1;h=n ;suc=0; while((j<=h)&&(!suc)) {mid =(j+h)/2; switch {case K=R[mid].key: suc=1; break; case K case K>R[mid].key: j=mid+1 } } if (suc) return(mid); else return(0); } 将上述算法中划线语句改为：K （１）改动后，算法能否正常工作？请说明原因。 （２）若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；若能正常工作，请给出一个查找序列和查找某个键值的比较次数。（本题６分，每小题３分） 6.有一组键值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大进行排序，请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。（本题６分） 五、设计题（共14分） 1．设棵二叉树以二叉链表为存储结构，结点结构为lchild |data |rchild 。设计一个算法，求在前根序列中处于第k个位置的结点。（本题６分） 2．设某单链表Ｌ的结点结构为data |next,试画出该链表的结构图，并用类Ｃ语言编写算法判断该链表的元素是否是递增的。（本题８分） 全真模拟试题(一)参考答案 一、单项选择题 1④ 2③ 3④分析：按题意，矩阵A是个三角矩阵，A[ I,j]的首地址可用下列公式计算： LOC（a ij）=LOC(a11)+(k-1)*L 其中K为A[I,j]在A中的序号k=I*(I-1)/2+j，L为每个元素所占的单元数。 所以有：LOC（a ij）=2000+（9*（9-1）/2+5-1）*4=2000+160=2160。故为答案④4．③ 5．④ 6．④ 7．① 8．②分析：如果G’为G的生成树，那么G’是G的子图，也是G的无环子图，并且还是G的极小连通子图，且V’=V，而连通分量则是指无向图的极大连通子图。故答案②是错误的。 9．④ 10。③ 11。④ 12。③ 二、判断题 1.v 2.x 3.v 4.v 5.x 6.x 7.x 8.v 9.v 10.x 三、填空题 1． R->next =s. 2． P->next= = NULL 3． Ls= =NULL 、ls=ls->link. 4． 12 分析：设n1=2,n2=3,n3=4, 树的总结点数为n=n0+ n1+n2+n3 树的分支数为n-1= n1+2n2+3n3 ②-①得：-1= n2+2n3-n0 有n0=n2+2n3+1=3+2*4+1=12 5．双亲表示法。 6． N-1 7． I,j,k. 8．冒泡排序、快速排序 9． T= =NULL、searchinsert(x,t->rchild). 四、应用题 1． EBFGCKHIJDA。 2．答案如图应用题I 9. 2.2 所示。 3． 3．分析：本题实际上是求最小生成树问题。由于衅中有两条权值为6的边，故可以得到两种方案。答案如图应用题I 9. 3.2 所示。 4．答案： （1）答案如图应用题I 9. 4.2 所示。 （2）v1 v2 v4 v5 v3和 v1 v4 v2 v3 v5。 5．（1）经过改动以后，有可能出现死循环，比如当查找的键值K小于有序表中的最小键值时，就会出现死循环。故算法不能正常进行。 （2）假设有序表的查找序列为（2，3，4，5，6），当待查的键值K=1时，出现死循环。 6．答案： 25 84 21 47 15 27 68 35 24 第一趟 [24 15 21] 25 [47 27 68 35 84] 第二趟 [21 15] 24 25 [35 27] 47 [68 84] 第三趟 [15] 21 24 25 [27] 35 47 68 [84] 得到 15 21 24 25 27 35 47 68 84 第一趟排序过程中键值的移动情况如下： 第一趟： [25 84 21 47 15 27 68 35 24 ] 一次交换之后 [24 84 21 47 15 27 68 35 25] 二次交换之后 [24 25 21 47 15 27 68 35 84] [24 25 21 47 15 27 68 35 84] [24 25 21 47 15 27 68 35 84] [24 25 21 47 15 27 68 35 84] 三次交换之后 [24 15 21 47 25 27 68 35 84] [24 15 21 47 25 27 68 35 84] 四次交换之后 [24 15 21 25 47 27 68 35 84] 以上“-”表示当前经比较不交换位置的元素。“ ”表示当前经比较交换位置的元素。五、设计题 1． Bitreptr search(bitreptr t ,int k) {if (t!=null) {count++; if (count= =k)return (t); else {search(t->lchild,k); search(t->rchild,k); } } } 2. 单链表L的结构如图设计题I 9. 2.2所示。 Int isviser(lklist L) {p=L; while(p->next!=null) if (p->data return(1); } 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。 Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向 的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p； Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ） Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序 列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结 点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分） 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈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 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i 1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈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 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2) 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 一、填空题（将正确的答案写入答题纸中。每空1分，共20分） ，_ DataNode__ _和 4、HBase中通过_ HDFS__ _存储底层数据,通过_ _Zookeeper_ _提供消息通信机制 5、HIVE默认采用_ _Derby _ __ __ _数据库进行元数据的存储，而真实的数据是存储在_ __HDFS __ __ _中。 6、如何在浏览器中查看HDFS 7、HDFS中当前block大小为128M,如果当前要上传到HDFS中的文件大小为300M，那 block进行存储。 8、HDFS 获取根目录下的文件列表的命令shell命令是_hadoop fs -ls -R / __ __ __ __ __ _；根目录下创建hdfs文件夹的shell命令是_ _hadoop fs -mkdir /hdfs__ __ __ __ _ 。 9、Y ARN架构中整个集群同一时间提供服务的ResourceManager有_ 1__ _个，负责集群资源的统一管理和调度。 二、选择题（将正确的答案写入答题纸中。每题2分，共20分） 1、配置Hadoop时，JA V A_HOME包含在哪一个配置文件中(B) A．hadoop-default.xml B．hadoop-env.sh C．hadoop-site.xml D．configuration.xs 2、下面哪个程序负责HDFS 数据存储。（C） A)NameNode B)Jobtracker C)Datanode D)secondaryNameNode 3、下列关于Hadoop API的说法错误的是（A） A．Hadoop的文件API不是通用的，只用于HDFS文件系统 B．Configuration类的默认实例化方法是以HDFS系统的资源配置为基础的C．FileStatus对象存储文件和目录的元数据 D．FSDataInputStream是java.io.DataInputStream的子类 4、HDfS 中的block 默认保存几份? （A） A)3 份 B)2 份 C)1 份 D)不确定 一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 数据结构试卷带答案 问题说明 部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我 （1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材 （2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题 （3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6 （4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足ki>=k2i p->rlink->llink=p->llink;此外，注意课堂中讲的指针名和操作方法 （12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。 （13）第5套选择第8题答案应为A:设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A) abedfc (14)第5套应用题第3题题目未指明查找方法，没法作 （15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B) 高度等于其结点数 （16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p；s->right=p->right；___p->right_______=s；s->right->left=s；（设结点中的两个指针域分别为left和right）。（17）第8套填空题第8题答案错 （18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。 (C) 42，40，55，60，80，85 （17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。(18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材 （19）第9套填空第4题答案错，9个元素冒泡排序，第一趟比较次数为8，最多8趟 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 第1章绪论 一、判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（×） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√） 7.数据的存储结构是数据的逻辑结构的存储映象。（√） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和步骤的描述。（√） 二、填空题 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算法和事后统计法。 16.一个算法的时间复杂度是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。 18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。 19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。 20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学 科。 三、选择题 1.数据结构通常是研究数据的（A）及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑 2.在逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．部结构和外部结构。 3.数据在计算机存储表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。 A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构 4.非线性结构中的每个结点（D）。 A．无直接前驱结点．B．无直接后继结点． 《数据结构》试卷B 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈 只能在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除 运算的一端称为。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间 的和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查 找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的 （）6. 栈和队列是一种非线性数据结构。 （）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 2017贵州大数据考试题目和答案 ? 1.大数据元年是指（单选题1分）得分：1分 o A.2010年 o B.2011年 o C.2012年 o D.2013年 ? 2.《国务院办公厅关于促进和规范健康医疗大数据应用发展的指导意见》提出，到2020年，统筹区域布局，依托现有资源建成（）区域临床医学数据示范中心。（单选题1分）得分：1分 o A.100个 o B.200个 o C.300个 o D.400个 ? 3.近几年，我国电子信息产业一直保持了（）以上的年增长速度，成为国民经济各个领域中间的佼佼者。（单选题1分）得分：1分 o A.7% o B.8% o C.9% o D.10% ? 4.宁家骏委员指出，过去我们研制一个新型号的航天器，平均需要多长时间？（单选题1分）得分：1分 o A.1-2年 o B.3-4年 o C.5-6年 o D.7-8年 ? 5.具体来说，摩尔定律就是每（）个月，产品的性能将提高一倍。（单选题1分）得分：1分 o A.6 o B.12 o C.16 o D.18 ? 6.以下说法错误的是哪项？（单选题1分）得分：1分 o A.大数据是一种思维方式 o B.大数据不仅仅是讲数据的体量大 o C.大数据会带来机器智能 o D.大数据的英文名称是large data ?7.第一个提出大数据概念的公司是（单选题1分）得分：1分 o A.微软公司 o B.脸谱公司 o C.谷歌公司 o D.麦肯锡公司 ?8.大数据要求企业设置的岗位是（单选题1分）得分：0分 o A.首席分析师和首席工程师 o B.首席信息官和首席工程师 o C.首席分析师和首席数据官 o D.首席信息官和首席数据官 ?9.世界上第一台电子计算机（ENIAC）是在哪一年宣告诞生的？（单选题1分）得分：1分 o A.1946年 o B.1947年 一、选择题 1、一个n个顶点的无向连通图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn 2、以下数据结构中，（）是非线性数据结构。 A．树B．字符串C．队列D．栈 3、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为（）。 A．n –i+1 B．n –i C．i D．i-1 4、与线性表的链接存贮不相符合的特性是（）。 A．便于插、删运算B．需要连续的存贮空间 C．只能顺序查找D．存贮空间动态分配 5、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数 为（）。 A．(rear-front+m)%m B．rear-front+1 C．(front+rear+m)%m D．(rear-front)%m 6、一个有n个顶点的无向图最多有( )条边。 A．n(n-1)/2 B．n (n-1) C．n-1 D．n+1 7、设栈的入栈序列是1，2，3，4，则（）不可能是其出栈序列。 A．1，2，4，3 B．2，1，3，4 C．1，4，3，2 D．4，3，1，2， 8、从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．初等结构、构造型结构 C．线性结构、非线性结构D．树型结构、图型结构 9、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（） A．空或只有一个根结点B．高度等于其结点数 C．任一结点无左孩子D．任一结点无右孩子 10、已知一个有向图用邻接矩阵表示，要删除所有从第i个结点发出的边，应该（）。 A．将邻接矩阵的第i 行删除B．将邻接矩阵的第i 行元素全部置零 C．将邻接矩阵的第i 列删除D．将邻接矩阵的第i 列元素全部置零 11、算法分析的两个主要方面是（） A．空间复杂性和时间复杂性B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 12、线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 13、具有6个顶点的无向连通图的生成树应有（）条边。 A．5 B．6 C．7 D．8 14、设栈的输入序列是A、B、C，则（）不可能是其出栈序列。 A．CBA B．CAB C．BCA D．ACB 15、有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为（）。 A．head==NULL B．head->next==NULL C．head->next== head D．head ！=NULL 16、栈和队都是（） A．顺序存储的线性结构B．链式存储的非线性结构 C．限制存取点的线性结构D．限制存取点的非线性结构 17、在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。 A．①②③B．②③④C．②④D．①④ 18、以下数据结构中，（）是非线性数据结构。 数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】数据结构试题及答案10套
数据结构试题库答案
数据结构试卷带答案
数据结构复习题(附答案)
《数据结构》题库及答案
大数据试题
数据结构复习题附答案
数据结构试题及答案(10套最新)
数据结构试卷带答案
2015年数据结构期末考试题及答案
算法与数据结构题库与答案
数据结构试题及答案
数据结构练习试题和答案解析
数据结构试卷B卷(含答案)
2017贵州大数据考试题目和答案
数据结构复习题及答案
数据结构试题(含答案)
数据结构考试题库含参考答案