数据结构与算法笔试题吐血整理

数据结构试题及答案

一、单项选择题

(1)          一个算法应该是（B   ）。

A) 程序                                                      B) 问题求解步骤的描述     

C) 要满足五个基本属性                           D) A和C

(2)          算法指的是（ D  ）。

A) 计算机程序                                             B) 解决问题的计算方法

C) 排序算法                                               D) 解决问题的有限运算序列。

(3)          与数据元素本身的形式、内容、相对位置、个数无关的是数据的（   B）。

A) 存储结构            B) 逻辑结构            C) 算法                   D)操作

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

A) 动态结构、静态结构                            B) 顺序结构、链式结构 

C) 线性结构、非线性结构                          D) 初等结构、构造型结构  　　

(5)          下列叙述中正确的是(   D )。

　　A）一个逻辑数据结构只能有一种存储结构

　　B）数据的逻辑结构属于线性结构，存储结构属于非线性结构

　　C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

(6)          数据的基本单位是（　　A　）

       A) 数据项                   B) 数据类型               C) 数据元素               D) 数据变量

(7)          下列程序的时间复杂度为（　　　）

i=0；s=0；

while（snext->next= =rear

(17)       从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（A　　）。

A)n-i                           B)n-i+1                        C)n-i-1                         D)i

(18)       已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（　　）。

A)1                             B)2                              C)3                              D)4

(19)       假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是（　　）。

A) R[3][3][3]                B) R[3][3][4]                C) R[4][3][5]                D) R[4][3][4]

(20)       设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（　　）。

A) 13                           B) 35                           C) 17                           D) 36

(21)       线性表采用链式存储时，节点的存储的地址（  B   ）。

A) 必须是不连续的                                   B) 连续与否均可

C) 必须是连续的                                     D) 和头节点的存储地址相连续

(22)       用链表表示线性表的优点是（  D ）。

A) 便于随机存取                               B) 花费的存储空间比顺序表少

C) 数据元素的物理顺序与逻辑顺序相同     D) 便于插入与删除

(23)       链表不具有的特点是（B   ） 。

A) 插入、删除不需要移动元素                 B) 可随机访问任一元素

C) 不必事先估计存储空间                      D) 所需空间与线性长度成正比

(24)       在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为(  D  )。

A) n-i+1 　　　          B) i　　                  C) i+1 　　　　          D) n-i

(25)       采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（  D  ）。

A) n　　　               B) n/2　　                C) (n-1)/2 　　　　     D) (n+1)/2

(26)       将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ B   ）。

A) O(1)                  B) O(n)                  C) O(m)                 D) O(m+n)

(27)       若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( A   )。

A) head==NULL 　　  B) head->next==NULL  C) head!=NULL　　     D) head->next==head

(28)       某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（  D  ）存储方式最节省运算时间。

A) 单链表                                                  B) 仅有头指针的单循环链表

C) 双链表                                                   D) 仅有尾指针的单循环链表

(29)       若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（　A　　）。

       A) 栈                          B) 线性表                   C) 队列                       D) 二叉排序树

(30)       顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（　D　　）。

A) s.elem［top］=e；   s.top=s.top+1；            B) s.elem［top+1］=e；s.top=s.top+1；                              

C) s.top=s.top+1； s.elem［top+1］=e；           D) s.top=s.top+1；s.elem［top］=e；                           

(31)       循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（　C　　）。

A) 8                            B) 16                          C) 17                          D) 18

(32)       链式栈与顺序栈相比，一个比较明显的优点是（  B  ）。

A) 插入操作更加方便                               B) 通常不会出现栈满的情况

C) 不会出现栈空的情况                              D) 删除操作更加方便

(33)       一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（ B ）。

A) 较快                 B) 较慢                C) 相同                 D) 不定

(34)       若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，若p1= =n,则pi为（ C  ）。

       A) i                        B) n= =i                C) n-i+1                 D) 不确定

(35)       一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是( C  ) 。

A) edcba                   B) decba                   C) dceab                   D) abcde

(36)       若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( D  )。

A) 2，4，3，1，5，6　　                              B) 3，2，4，1，6，5

C) 4，3，2，1，5，6 　　                             D) 2，3，5，1，6，4

(37)       对于栈操作数据的原则是（ B  ）。

A) 先进先出             B) 后进先出             C) 后进后出            D) 不分顺序

(38)       栈和队列的共同点是（  C  ）。

A) 都是先进先出                          B) 都是先进后出  

C) 只允许在端点处插入和删除元素          D) 没有共同点

(39)       一个队列的入队序列是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

(40)       设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出对操作后其头指针front值为（D  ）。

A)  front=front+1                                         B)  front=(front+1)%(m-1)  

C)  front=(front-1)%m                                  D)  front=(front+1)%m

(41)       引起循环队列队头位置发生变化的操作是(  A  )。

A) 出队                       B) 入队　　              C) 取队头元素            D) 取队尾元素

(2)      设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（  A  ）。

A）(rear-front+m)%m  B）rear-front+1            C）(front-rear+m)%m  D）(rear-front)%m

(42)       二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且A[0][0]地址为150，则元素A[9][7]的地址为(  A  )。

A) 429　　　　　       B) 432　　              C) 435 　　　　　      D) 438

(43)       设有一个10阶的对称矩阵A[10][10]，采用压缩方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[8][5]在B[]中（  C ）位置。

A) 32                         B) 33　　               C) 41                        D) 65

(44)       若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（inext

(154) 在一个带头节点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=                   。p->next->next

(155) 设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:          py->next=px->next; px->next=py。

(156)         对于栈操作数据的原则是                   。后进先出

(157)         设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为                   。(rear-front+m)%m

(158) 若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，若p1= =n,则pi为                   。n-i+1    

(159)            队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

(160) 通常程序在调用另一个程序时，都需要使用一个       栈来保存被调用程序内分配的局部变量。形式参数的存储空间以及返回地址。

(161) 栈下溢是指在___栈空_____时进行出栈操作。

(162) 用P表示入栈操作，D表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的P和D的操作串为_______ 。PDPPDPDD

(163) 在具有n个单元的循环队列中，队满共有          n-1个元素。

(164)            队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

(165) 循环队列的引入，目的是为了克服_______假溢出。

(166) 所谓稀疏矩阵指的是_______非零元很少(tnext=NULL;

while((1)________)

   {q=p; p=p->next; q->next=h->next; h->next=(2)________;   }

}

(1)p!=null       ∥链表未到尾就一直作

(2)q             ∥将当前结点作为头结点后的第一元素结点插入

(236) 下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。

void  reverse（linklist &L）{

p=null；q=L；

while（q！=null）

{ (1)      ;   q->next=p；p=q；(2)___  ; }

               (3)_____;

}

(1) L=L->next;  ∥暂存后继

(2)q=L;        ∥待逆置结点

(3)L=p;        ∥头指针仍为L

(237) 以下算法的功能是用头插法建立单链表的算法，请填空完善之。

   Linklist  CreateFromHead(  )

    {      LinkList   L;

               Node   *s;

              char     c;

              L=(Linklist)malloc(sizeof(Node));                   /*为头结点分配存储空间*/

                                    L->next=NULL  ;

                While( (  c=getchar())  !=’*’  )

                {   s=(Node*)malloc(sizeof(Node));            /*为读入的字符分配存储空间*/

s->data=c;

                      s->next=L->next  ;

                      L->next=s   ;

}

        return L;

}

(238) 以下算法的功能是尾插法创建链表，请填空完善之。

typedef struct Node  /*结点类型定义*/

{   char data;

    struct Node  * next;

}  Node, *LinkList;  /* LinkList为结构指针类型*/

Linklist  CreateFromTail(  )                        /*将新增的字符追加到链表的末尾*/

{         LinkList L;

          Node *r, *s;

        char  c;  

          L=(Node * )malloc(sizeof(Node));                       /*为头结点分配存储空间*/

        L->next=NULL;

        r=L;          /*r指针指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/

       while(  (                      c=getchar()) !=’$’  )                         /*当输入‘$’时，建表结束*/

{        s=(Node*)malloc(sizeof(Node));   s->data=c;

                 ；r->next=s;   r=s; 

}

            ；  r->next=NULL        /*将最后一个结点的next链域置为空，表示链表的结束*/

return L;

}     /*CreateFromTail*/ 

(239) 下列算法在顺序表L中依次存放着线性表中的元素，在表中查找与e相等的元素，若 L.elem[i]=e,则找到该元素，并返回i+1，若找不到，则返回“-1”  ，请填空完善之。

 int  Locate(SeqList L，int e)

{       i=0 ;                      /*i为扫描计数器，初值为0，即从第一个元素开始比较*/

      while ((ilast+2，请填空完善之。 

void   InsList(SeqList *L, int i,  int e)

{   int k;

if((iL->last+2))   printf(“插入位置i值不合法”)；

     if(L->last>=maxsize-1)    printf(“表已满无法插入”)；

for(k=L->last;k>=i-1;k--)          /*为插入元素而移动位置*/

                                 L->elem[k+1]=L->elem[k] ;

                 L->elem[i-1]=e ;     /*在C语言数组中，第i个元素的下标为i-1*/

                  L->last++ ;

   }

(241) 下列算法是在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1，请填空完善之。

 int  DelList(SeqList *L, int i, int *e)

{     int k;

if((i                L->last+1  ))     printf(“删除位置不合法！”)；

                  *e= L->elem[i-1] ;      /* 将删除的元素存放到e所指向的变量中*/

for(k=i;ilast;k++)

                        L->elem[k-1]= L->elem[k]  ;        /*将后面的元素依次前移*/

                  L->last--  ;

}

四、解答题

(242) 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。

　　(1) 写出队满的条件表达式；

　　(2) 写出队空的条件表达式；

　　(3) 设m=40,rear=13,quelen=19,求队头元素的位置；

　　(4) 写出一般情况下队头元素位置的表达式。

(1) quelen == m

(2) quelen == 0

(3) ( 13 - 19 + 40 ) % 40 = 34

(4) ( rear - quelen + m ) % m

(243) 已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。

　    B

        /   \

       A     F

            / \

           E   G

          /

         C

          \

           D

(244) 已知一棵二叉树的前序序列为ABCDEFGH，中序序列为CBEDFAGH，请画出该二叉树。

           A

              /   \

            B     G

             /   \    \

           C     D    H

               /  \

             E    F

(245) 已知一棵二叉树如图所示。请分别写出按前序、中序、后序和层次遍历是得到的顶点序列。

前序：A,B,D,G,C,E,F,H

中序：D,G,B,A,E,C,H,F

后序：G,D,B,E,H,F,C,A

层次：A,B,C,D,E,F,G,H

(246) 已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H, A,C,K,I,L,F。

(1)   写出该二叉树的后序序列；

(2)   画出该二叉树；

(3)   求该二叉树的高度(假定空树的高度为－1)和度为2、度为1、及度为0的结点个数。

该二叉树的后序序列为：J,G,D,H,E,B,K,L,I,F,C,A。

该二叉树的形式如图所示：

该二叉树高度为：5。

度为2的结点的个数为：3。

度为1的结点的个数为：5。

度为0的结点个数为：4。

(247) 有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，并求其加权路径长度WPL，字符c的编码。

WPL＝80 字符c：001（不唯一）

(4)      下图是带权的有向图G的邻接表表示法。从结点V1出发，求出：

a)         深度遍历图G；

b)        G的一个拓扑序列；

c)         从结点V1到结点V8的最短路径。

参考答案：v1,v2,v3,v8,v4,v5,v7,v6  (2分)

v1,v2,v4,v6,v5,v3,v7,v8  (2分)

V1到结点V8的最短路径为：v1,v2,v3,v8  (2分)

(248) 已知如图所示的有向图，请给出该图的：

（1）       每个顶点的入度、出度；

（2）       邻接矩阵；

（3）       邻接表；

(249) 对下面的有向图，从顶点V1开始进行遍历，试画出遍历得到的DFS生成森林和BFS生成森林。

图全对给4分，错一个顶点扣1分，扣完为止。

遍历得到的DFS生成森林和BFS生成森林如下图：

(250) 采用哈希函数Ｈ(k)=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51

（1）构造哈希表（画示意图）；

（2）装填因子；等概率下

（3）成功的和（4）不成功的平均查找长度

1）

散列地址

0

1

2

3

4

5

6

7

8

9

10

11

12

关键字

13

22

53

1

41

67

46

51

30

比较次数

1

1

1

2

1

2

1

1

1

（2）装填因子=9/13=0.7    （3）ASLsucc =11/9         （4）ASLunsucc =29/13

(251) 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

散列地址

0

1

2

3

4

5

6

7

8

9

关键字

14

01

9

23

84

27

55

20

比较次数

1

1

1

2

 3 

4

1

2

平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8

以关键字27为例：H（27）=27%7=6（冲突）   H1=（6+1）%10=7（冲突）

H2=（6+22）%10=0（冲突）   H3=（6+33）%10=5   所以比较了4次。

(252) 对于给定的一组记录的关键字{ 23,13,17,21,30,60,58,28,30,90},试分别写出冒泡排序、快速排序、堆排序、归并排序第一趟排序后的结果。

冒泡排序13,23,17,21,,28,30,60,58,30*, 90

快速排序：(21,13,17,) 13,( 30,60,58,28,30*,90 )

堆排序： 13,21,17,23,30,60,58,28,30*,90,

归并排序按层遍历：(13  23)  (17 21 )  (30  60 )  ( 28  58 )   (30*  90)

(253) 采用哈希函数Ｈ(k)=2*k mod 13并用链地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51进行下列工作：

（a）构造哈希表（画示意图）；

（b）等概率下成功的和不成功的平均查找长度。

参考答案：链地址表全对给8分。错一个结点扣1分，扣完为止。

0

→

13

^

1

→

46

^

2

→

53

→

1

^

3

^

4

→

41

→

67

^

5

→

22

^

6

^

7

^

8

→

30

^

9

^

10

^

11

→

51

^

12

^

ASLsucc=(7+4)/13=11/9（1分）    ASLunsucc=(5+4)/13=9/13（1分）

　四、算法设计题(10分)

(254) 阅读下列递归算法，写出非递归方法实现相同功能的C程序。

void  test(int  &sum)

        { int  x；

          scanf(x)；

          if(x=0) sum=0 else {test(sum); sum+=x;}

          printf(sum)；

        }

＃include   (1分)

void main()   (1分)

{  int x,sum=0,top=0,s[];   (1分)

       scanf(“%d”,&x)

       while (x0)

           { s[++top]:=a; scanf(“%d”,&x); }(3分)

       while (top)

           sum+=s[top--]; (3分)

printf(“%d”,sum); (1分)

     }

(255) 试写出把图的邻接矩阵表示转换为邻接表表示的算法。

设图的邻接矩阵为g[n][n]（针对无向图），定义邻接表节点的类型为

struct edgenode

{  int adjvex;

   edgenode  next;

}

typedef  edgenode  *adjlist[n];

void matritolist (int g[][], adjlist gl, int n )

{    edgenode *p, *q;

  for (int i=0 inext=p;        q=p;  }

}

}

(256) 阅读算法并根据输入数据画出链表。

linklist createlistr1(  )

{    char  ch;

     linklist      head=(listnode*)malloc(sizeof(listnode));

     listnode  *p，*r；               

     r=head;

     while((ch=getchar( ))!=‵\n′)

     {     p=(listnode*)malloc(sizeof(listnode));

           while  (p)  p=(listnode*)malloc(sizeof(listnode));

           p–>data=ch;       r–>next=p;         r=p;

     }

     r–>next=NULL;

     return(head);

}

输入数据为：text8

(257) 阅读算法并指出下列各段程序完成的功能。

void  add_poly(Lnode *pa,Lnode *pb)

{  Lnode *p,*q,*u,*pre;   int x;

   p=pa->next;   q=pb->next;   pre=pa;

   while((p!=NULL) && ((q!=NULL))

   {   if   (p->exp < q->exp)

           {   pre=p;  p=p->next;       }

       else    if (p->exp= =q->exp)

                  {  x=p->coef+q->coef;       

if  (x!=0) { p->coef=x;  pre=p;}

                     else    { pre->next=p->next;  free(p); }

                     p=pre->next;    u=q;    q=q->next;

                     free(u);

                   }

               else

                   {    u=q->next;q->next=p;pre->next=q;

                        pre=q;  q=u;

                    }

     }

if (q!=NULL)   pre->next=q;

     free(pb);

}

 两个多项式相加

(258) 阅读下面的程序，说明程序的具体功能。

typedef int elementype

typedef struct node

{  elemtype  data;

strunct node  *next;

}linklist;

void function( linklist *head, elemtype x )

{  linklist *q, *p;

q=head;

p=q-next;

while (p !=NULL) && (p->data != x )

{  q=p;  p=p->next;  }

if  (q==NULL)   printf (“there is no this node ::\n”);

else  {  q ->next =p ->next ;  free (p);    }

}

该程序的功能是：在带头结点的单链表中，删除单链表中枝为z的数据元素。

(259) 阅读下面的程序，说明程序的具体功能。

void function(  )

      {      initstack(s);

              scanf (“%”,n);

              while(n)

              {      push(s,n%8);         n=n/8;         }

              while(! Stackempty(s))

              {       pop(s,e);            printf(“%d”,e);     }

        }

该程序的功能是：10进制数转换为8进制

(260) 阅读下面的程序，说明程序的具体功能。

void    print(int  w)

{      int  i;

       if ( w!=0)

       {     print(w-1);

             for(i=1;idata)

          inorder(p–>rchild);

      }

}

(264) 阅读下面的程序，分别指出程序中三个for循环、整个程序以及语句scanf("%d,%d",&G.vexnum,&G.arcnum);  的功能。

void funcgraph(MGraph &G)

{     int i,j,k,w;      char v1,v2;

       printf("Input vexnum & arcnum:");

       scanf("%d,%d",&G.vexnum,&G.arcnum);

       printf("Input Vertices:");

       for (i=0;i