数据结构试题及答案

A、 指针 B、 引用 C、 值

D、函数

（ ）77.下面程序段的时间复杂度为____________。 for(int i=0; i

A、 O(m2) B、 O(n2) C、 O(m*n) D、 O(m+n)

（ ）78. 执行下面程序段时，执行S语句的次数为____________。 for(int i=1; i<=n; i++) for(int j=1; j<=i; j++) S;

A、 n2 B、 n2/2 C、 n(n+1) D、 n(n+1)/2

（ ）79. 下面算法的时间复杂度为____________。 int f( unsigned int n ) {

if ( n==0 || n==1 ) return 1; else return n*f(n-1); }

A、 O(1) B、 O(n) C、 O(n2) D、 O(n!)

（ ）80．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移 个元素。

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

（ ）81．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移_____个元素。

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

（ ）82.在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为_____。

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

（ ）83．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行_____ 。

A、HL = p; p->next = HL; C、p->next = HL; p = HL;

B、p->next = HL; HL = p; D、p->next = HL->next; HL->next = p;

（ ）84．在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行_____。

A、q->next = p->next ; p->next = q; C、q->next = p->next; p->next = q; B、p->next = q->next; q = p; D、p->next = q->next ; q->next = p;

（ ）85．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行_____。

A、p = q->next ; p->next = q->next; C、p = q->next ; q->next = p->next; B、p = q->next ; q->next = p; D、q->next = q->next->next; q->next = q;

（ ）86. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的________。

A、 行号 B、 列号 C、 元素值 D、 地址

（ ）87. 设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为_______。

A、 O(1) B、 O(n) C、 O(n2) D、 O(log2n)

（ ）88．栈的插入与删除操作在_____进行。

A、栈顶 B、栈底 C、任意位置 D、指定位置

（ ）89．当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行_____语句修改top指针。

A、top++ B、top-- C、top=0 D、top

（ ）90．若让元素1，2，3依次进栈，则出栈次序不可能出现_____种情况。

A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2

（ ）91．在一个循环顺序队列中，队首指针指向队首元素的_____位置。

A、前一个 B、后一个 C、当前 D、后面

（ ）92．当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为_____。

A、N-2 B、N-1 C、N D、N+1

（ ）93．从一个循环顺序队列删除元素时，首先需要_____。

A、前移一位队首指针 B、后移一位队首指针

C、取出队首指针所指位置上的元素 D、取出队尾指针所指位置上的元素

（ ）94．假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是_____。

A、f+1==r B、r+1==f C、f==0 D、f==r

（ ）95．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是_____。

A、front==rear B、front!=NULL C、rear!=NULL D、front==NULL

四、应用题：

1、栈和队列都是特殊线性表，其特殊性是什么

2、设有一顺序队列sq，容量为5，初始状态==0，划出作完下列操作的队列及其头尾指针变化状态，若不能入队，简述理由后停止。 1）d,e,b 入队。 2）d,e 出队。 3） i,j 入队。 4）b 出队。 5）n,o,p 入队。 3、设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少

4、将两个栈存入数组V[1..m]中应如何安排最好这时栈空、栈满的条件是什么 5、已知稀疏矩阵如下：

请写出该稀疏矩阵三元组表示。

6、广义表A=（a,b,(c,d),(e,(f,g))）,求其长度，及深度。 7、请画出下面广义表相应的加入表头结点的单链表表示，

D(A(x,y,L(a,b))，B(z,A(x,y,L(a,b))))。

8、一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）

9、设二叉树后根遍历为BAC，画出所有可能的二叉树。

10、假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。

11、有一个完全二叉树按层次顺序存放在一维数组中，如下所示：

请指出结点P的父结点，左子女，右子女。 12、给出下列二叉树的先序序列。

13、已知某非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，

即

ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为：

14、设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树。 15、已知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入生成的

一棵二叉树。

16、由于元素插入的次序不同，所构成的二叉排序树也有不同的状态，请画出一棵含有1，2，

3，4，5，6六个结点且以1为根，深度为4的二叉排序树。 17、什么是线索二叉树为什么要线索化

18、有n个顶点的有向连通图最多有多少条边最少有多少条边 19、下图中给出由7个顶点组成的无向图。从顶点1出发，

对它进行深度优先遍历得到的顶点序列是： 进行广度优先遍历得到的顶点序列是：

20、什么是连通图的生成树

21、什么是哈夫曼（Huffman）树

22、已知结点a,b,c,d及其权值写出哈夫曼树的构造过程。 a b c d 7 5 2 4 23、已知图G={V , E} V={ a, b, c, d, e }

E={(a, b),(b, d),(c, d),(d, e),(e, a),(a, c)} 画出图G，画出图G的邻接表。

24、考虑下图：

1）从顶点A出发，求它的深度优先生成树。 2）从顶点E出发，求它的广度优先生成树。

3）根据普里姆（Prim）算法，求它的最小生成树。

25、设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行

排序。

若采用初始步长为4的Shell排序法，则一趟扫描的结果是：

若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是：

26、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为

基准而得到的第一次划分结果为：

27、用二分法对一个长度为10的有序表进行查找，填写查找每个元素需要的比较次数。 下标： 0 1 2 3 4 5 6 7 8 9 比较次数：

28、若对序列(49,38,27,13,97,76,50,65)采用泡排序法(按照值的大小从小到大)进行排序，请分别在下

表中写出每一趟排序的结果。

原始序列 49 38 27 13 97 76 50 65 第1趟的结果 第2趟的结果 第3趟的结果 第4趟的结果

29、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序

时的变化过程：

1）归并排序 每归并一次书写一个次序。

2）快速排序 每划分一次书写一个次序。

3）堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

30、给出一组关键字T=（12，2，16，30，8，28，4，10，20，6，18）。写出用下列算法从小到大

排序时第一趟结束时的序列：

1）希尔排序（第一趟排序的增量为5） 2）快速排序(选第一个记录为枢轴(分隔)) 3）链式基数排序（基数为10）

31、若杂凑表的地址范围为[0:9]，杂凑函数为H(key)=(key2+2)MOD 9，并且采用链地址方法处理冲