数据结构考试试题(带答案).doc

系别 班次 学号 姓名
××科技大学成都学院二零零八至二零零九学年第一学期
数据结构 课堂测试（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个字节,由大写字母表示）组成，如下所示：

其中指针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（aij ，l≤i,j≤ 10）的元素满足：
aij≠0(i≥j, l≤i, j≤ 10)
aij=0 (i<j, l≤i, j≤ 10)
现将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,…, kn},对i=1,2,…,|_n/2_|,满足(      )
①ki≤k2i≤k2i+1                ②ki<k2i+1<k2i
③ki≤k2i且ki≤k2i+1(2i+1≤n)   ④ki≤k2i 或ki≤k2i+1(2i+1≤n)
二、         判断题（判断下列各题是否正确，正确在括号内打“V”，错的找“X”。每小题1分，共10分）
1．  双链表中至多只有一个结点的后继指针为空。（    ）
2．  在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（     ）
3．  对链表进行插入和删除操作时，不必移动结点。（      ）
4．  栈可以作为实现程序设计语言过程调用时的一种数据结构。（    ）
5．  在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。(   )i
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中若有弧<vi,vj>、<vj,vk>和<vi,vk>, 则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为______________。
8．  设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行（按递增排序），　　　　　最省时间，　　　　　最费时间。
9．  下面是将键值为x 的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。
typedef struct pnode
  {int key;
   struct pnode   *left,   *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<t->key) searchinsert(x,t->lchild)
         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<R[mid].key:  h=mid-1; break;
        case K>R[mid].key:  j=mid+1
       }
    }
   if (suc)  return(mid);  else return(0);
}
将上述算法中划线语句改为：K<R[mid].key:  h=mid.
（１）           改动后，算法能否正常工作？请说明原因。
（２）           若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；若能正常工作，请给出一个查找序列和查找某个键值的比较次数。（本题６分，每小题３分）
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（aij）=LOC(a11)+(k-1)*L
        其中K为A[I,j]在A中的序号k=I*(I-1)/2+j，L为每个元素所占的单元数。
  所以有：LOC（aij）=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 <p->next->data) p=p->next;
else return(0);
 return(1);
}

第 14 页 共 14页