Question

求下面数据结构试题的答案...

1．算法的计算量大小称为计算的（ ）
2．从逻辑上，可以把数据结构分为（ ）两大类。
3．下述哪一条是顺序存储结构的优点？（ ）
4．线性表是具有n个（ ）的有限序列（n>0）。
5．对于栈操作数据的原则是（ ）。
6．当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为（ ）。
7．用链表方式存储的队列，在进行删除运算时（ ）
9．设广义表 L=((a,b,c))，则L的长度和深度分别为（ ）
10．已知一算术表达式的中序遍历结果为A+B*C-D/E,后序遍历的结果为ABC*+DE/-,其前序遍历的结果为（ ）。
11．在完全二叉树中，若一个结点是叶结点，则它没有（ ）。
12．图中有关路径的定义是（ ）。
13．设无向图的顶点个数为n，则该图最多有（ ）条边。
14．一个n 个顶点的连通无向图，其边个数至少为（ ）。
15．有n个叶子的哈夫曼树的结点总数为（ ）
17．顺序表是线性表的（ ）
19．循环链表主要优点是（ ）
20. 栈与一般线性表的主要区别是（ ）。
1、数据结构中评价算法的两个重要指标是（ ）。
2、 （ ）又称作先进先出表。
3、空格串是指（ ），其长度等于（）。
4、树在计算机内的表示方式有（ ），（ ），（ ）。
5、具有10个顶点的无向图，边的总数最多为（ ）。
6、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1，2，3，4，为了得到1，3，4，2，出栈顺序，相应的S和X的操作串为（ ）。
7、请写出下列语句段的时间复杂度
〈1〉for(i=1;i<=n;i++)
for(j=1;j<=i;j++) 答：
s++;
<2> for(i=1;i<=n;i++)
for(j=i;j<=n;j++) 答：
s++;
8、有7个带权结点，其权值分别为4，7，8，2，5，16，30，试以它们为叶子结点的权值构造一棵哈夫曼树（要求按每个结点的左子树根结点的权值小于或等于右子树根结点的权值的次序结构），并计算出其带权路径长度WPL。
9、请画出下图的临接矩阵和邻接表。

10、请把下图中的树转换成二叉树，并写出二叉树的前序、中序、后序遍历结果。
.

Answer 1

一．

1,复杂性   2.线性结构  非线性结构

3．可以按序号随机存取  4.数据元素   

5.后进先出  6.n    7.只能在队头进行

9.长度 1  深度  1

10  -+A*BC/DE

11

12 顶点Vp到顶点Vq之间的路径是指定的序列Vp，Vi1，Vi2•••Vim，Vq。

13 n（n-2）/2    14  n—1     15   2n—1

17 一种存储结构

19可以从表中任意结点开始遍历整个链表；只用一个指向尾结点的指针对链表头、尾进行操作，提高了效率。

20栈是仅限制在表的一端进行插入和删除的运算的线性表，是一种操作受限的线性表。

二．

1算法 的时间复杂度和空间复杂度

2.队列

3.

4嵌套集合表示法，广义表表示法，凹入表示法

5. 45    6.S(1) X(1) S(2)S(3)X(3)S(4)X(4)X(2)

7（1） O（nˆ2） 

 （2） O（nˆ2）

8.

哈夫曼树：

WPL=2*5+4*5+5*4+16*3+8*3+7*3+30=173

9.邻接矩阵：

邻接表：

10.二叉树：

前序：ABCEFD

中序：BEFCDA

后序：FEDCBA

Answer 2

全国2008年10月高等教育自学考试

数据结构试题

课程代码：02331

一、单项选择题(本大题共15小题，每小题2分，共30分)

在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）

A. 栈 B. 队列

C. 树 D. 图

2.下面程序段的时间复杂度为（ ）

for (i=0; i<m; i++)

for (j=0; j<n; j++)

A[i][j]=i*j;

A. O (m2) B. O (n2)

C. O (m*n) D. O (m+n)

3.在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（ ）

A. p->next==head B. p->next->next==head

C. p->next==NULL D. p==head

4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ ）

A. SXSSXXXX B. SXXSXSSX

C. SXSXXSSX D. SSSXXSXX

5.两个字符串相等的条件是（ ）

A. 串的长度相等 B. 含有相同的字符集

C. 都是非空串 D. 串的长度相等且对应的字符相同

6.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（ ）

A. head (tail (head (L))) B. head (head(head(L)))

C. tail (head (tail (L))) D. head (head (tail (L)))

7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）

A. 0 B. 1

C. 48 D. 49

8.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ）

A. Dout B. Dout-1

C. Dout+1 D. n

9.如图所示的有向无环图可以得到的拓扑序列的个数是（ ）

A. 3 B. 4

C. 5 D. 6

10.如图所示的带权无向图的最小生成树的权为（ ）

A. 51 B. 52

C. 54 D. 56

11.对长度为n的关键字序列进行堆排序的空间复杂度为（ ）

A. O（log2n） B. O（1）

C. O（n） D. O（n*log2n）

12.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为

（35，51，24，13，68，56，42，77，93）

（35，24，13，51，56，42，68，77，93）

所采用的排序方法是（ ）

A. 插入排序 B. 冒泡排序

C. 快速排序 D. 归并排序

13.已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（ ）

A. T[2] B. T[4]

C. T[8] D. T[10]

14.适宜进行批量处理的文件类型是（ ）

A. 顺序文件 B. 索引顺序文件

C. 散列文件 D. 多关键字文件

15.VSAM文件的索引结构为（ ）

A. B+树 B. 二叉排序树

C. B-树 D. 最优二叉树

二、填空题(本大题共10小题，每小题2分，共20分)

请在每小题的空格中填上正确答案。错填、不填均无分。

16.如果某算法对于规模为n的问题的时间耗费为T（n）=3n3，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的 倍。

17.将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时间复杂度是 。

18.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是 。

19.字符串“sgabacbadfgbacst” 中存在有 个与字符串“ba”相同的子串。

20.假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC（a00）,且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为 。

21.假设用<x,y>表示树的边（其中x是y的双亲），已知一棵树的边集为

，该树的度是 。

22.n个顶点且含有环路的无向连通图中，至少含有 条边。

23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 。

24.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对 结构也无特殊要求。

25.顺序文件中记录存放的物理顺序和 顺序一致。

三、解答题(本大题共4小题，每小题5分，共20分)

26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。

前序序列：

后序序列：

27.图的邻接表的类型定义如下所示：

#define MaxVertexNum 50

typedef struct node {

int adjvex;

struct node *next;

}EdgeNode;

typedef struct {

VertexType vertex;

EdgeNode *firstedge;

}VertexNode;

typedef VertexNode AdjList[MaxVertexNum];

typedef struct {

AdjList adjlist;

int n, e;

}ALGraph;

为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。

题27图

28.某类物品的编号由一个大写英文字母及2位数字（0..9）组成，形如E32。运用基数排序

对下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。

E13，A37，F43，B32，B47，E12，F37，B12

第一趟：

第二趟：

第三趟：

29.（1）画出对表长为13的有序顺序表进行二分查找的判定树；

（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。

（1）

（2）

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30.已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：

（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态；

（2）简述算法f30的功能。

void f30 (SeqList *L) {

int i,j;

for (i=j=0;i<L->length; i++)

if(L->data[i]>=0){

if(i!=j)L->data[j]=L->data[i];

j++；

}

L->length=j;

}

(1)

(2)

31.阅读下列算法，并回答问题：

（1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f31 (&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态；

（2）简述算法f31的功能。

（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）

void f31 (Queue*Q, Queue*Q1, Queue*Q2) {

int e;

lnitQueue (Q1);

lnitQueue (Q2);

while (!QueueEmpty (Q)) {

e=DeQueue (Q);

if (e>=0) EnQueue (Q1,e);

else EnQueue (Q2,e)

}

}

（1）

（2）

32.阅读下列算法，并回答问题：

（1）假设串由合法的英文字母和空格组成，并以’\0’作结束符。设串s=”⊔⊔|⊔am⊔a⊔⊔⊔student”(⊔表示空格符)，写出f32（s）的返回值；

（2）简述算法f32的功能。

int f32 (char*s){

int i, n, inword;

n=inword=0;

for (i=0;s[i]!=’\0’;i++)

if (s[i]!=’⊔’&& inword==0){

inword=1;

n++;

}

else if (s[i]==’⊔’&& inword==1)

inword=0;

return n;

}

（1）

（2）

33.阅读下列对正整数关键字序列L操作的算法，并回答问题：

（1）设L=(28,19,27,49,56,12,10,25,20,50),写出f33 (L,4)的返回值；

（2）简述函数f33的功能。

int Partition (SeqList*L, int low, int high);

‖对L[low..high]做划分，返回基准记录的位置，并使左部的关键字

‖都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字

int f33 (SeqList L, int k){

int low, high, pivotpos;

low=1;

high=L.length;

if (k<low || k>high)

return-1;

do {

pivotpos=Partition (&L, low, high);‖调用快速排序的划分算法

if (pivotpos<k)

low=pivotpos+1;

else if (pivotpos>k)

high=pivotpos-1;

}while (pivotpos!=k);

return L.data [pivotpos];

}

（1）

（2）

五、算法设计题（本题10分）

34.二叉排序树的类型定义如下：

typedef struct BSTNode {‖ 二叉排序树的结点结构

int data; ‖数据域

struct BSTNode *lchild, *rchild; ‖左、右孩子指针

}BSTNode,*BSTree;

设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。