数据结构安徽大学考试

安徽大学数据结构

一、填空题

1、算法的5个重要特性是_____有穷性_____、___确定性________、___可行性_____、输入和输出。

2、单链表中，除首元素结点外，其它任一元素结点的存储位置由__其前驱的指针域_________指示。

3、在双向链表中，欲在p所指结点之前插入一个由s指向的结点，请完成有关操作。 s->prior=p->prior; p->prior=s; p->next=s->next； s->next=p;

4、对于栈只能在____栈顶____插入和删除元素；对于队列只能在___队尾______插入元素和__队头_____删除元素。

5、在模式匹配的KMP算法中用到了一个next函数，若next[j]=k，则说明在模式串T中存在一个与“T1T2...Tk-1”相等的子串“__Tj-k+1?.Tj-1_______________”。

6、假设有二维数组A6?8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A共占用_____288_______个字节的存储单元，按行存储时，元素A25的第一个字节的地址为______1126_______。

8、若以{4，5，6，7，8 }作为叶子结点的权值构造哈夫曼树，则其带权路径长度为__69____。 9、广义表g=( ())的表头是_____( )_____，表尾是____( )______。

二、单项选择题

1、线性结构的顺序存储结构是一种?___A___的存储结构，线性结构的链式存储是一种?____B_的存储结构。

A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 2、执行下面程序段时，S 语句的执行次数为__A_______。 for (int i=1;i<=n-1;i++) for (int j=i+1;j<=n;j++) S;

A. n(n?1)/2 B. n2/2 C. n(n?1)/2 D. n

3、将两个各有N个元素的有序表归并为一个有序表，其最少的比较次数是__A______。 A. N; B. 2N-1; C. 2N; D. N-1

4、已知4个元素进栈的顺序依次为A,B,C,D，则下面哪一个出栈序列是不可能得到的__C___。 A. ABCD; B. CBAD; C. CADB; D. BCAD

5、G是一个非连通无向图，共有28条边，则该图至少有____B___个顶点。 A. 8 B. 9 C. 10 D. 12

6、某二叉树的层序序列是abcdefgh，中序序列是dbgehacf，则该树的后序序列是_______C_________。

A . fahgbec B. eagbfdc C. dghebfca D. acdbfge

三、应用题

1．对图2所示的二叉树，要求

图2

（1）将其转换为树或森林，画出转换后的结果。

（2）给出对该树或森林分别进行先根遍历和后根遍历得到的结点序列。 （1） A E G B C D F H I

(2) 先根ABCDEFGHI 后根 BCDAFEHIG

B C F D H I A E G 四、算法阅读题

1、阅读下面算法，按要求作答，其中Push(S, d)表示将数据元素d压入栈S中，Pop(T,d)表示T的栈顶元素出栈并存入d中。 int algo (Stack S , int e) {

int d; Stack T; InitStack(T);

while(!StackEmpty(S)) { Pop(S,d);

if(d!=e) Push(T, d);

} //while

while(!StackEmpty(T)) {

Pop(T, d); Push(S, d); } }

（1）假设栈S中的原始数据从栈底至栈顶依次为：3，5，7，12，5，6，8；e的值为5。请写出算法执行完后栈S中从栈底至栈顶的数据元素序列。 3 7 12 6 8

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

将栈S中所有等于e的元素利用栈T从S中删除

2、已知数组a中存放着两组数据元素序列（a0，a1，．．．，am-1，b0，b1，．．．，bn-1）。下面算法利用原存储空间将a中的数据元素序列就地互换为（b0，b1，．．．，bn-1，a0，a1，．．．，am-1），算法思想可以描述为：

（1）把数组a中的数据元素序列（a0，a1，．．．，am-1，b0，b1，．．．，bn-1）就地逆置为（bn-1，．．．，b1，b0，am-1，．．．，a1，a0）。

（2）把数组a中的数据元素序列（bn-1，．．．，b1，b0，am-1，．．．，a1，a0）就地逆置为（b0，b1，．．．， bn-1，am-1，．．．，a1，a0）。

(3) 把数组a中的数据元素序列（b0，b1，．．．， bn-1，am-1，．．．，a1，a0）就地逆置为（b0，b1，...， bn-1，a0，a1...，am-1）。

根据上述算法思想，请在空缺处填上适当的语句，以完善算法功能。 void converse (ElemType a[],int low,int high) { //将数组a中自下标low 至high的一段数据元素逆置

int n,i; ElemType x;

n= (high-low+1)/2; // n 为循环次数 for(i=0;i

?__a[low+i]=a[high-i]______; ?__a[high-i]=x__________; }

}

void exchange (ElemType a[],int m,int n) {

converse(a,0,m+n-1);//将数组a中的m+n个元素就地逆置 ?_converse(a,0,n-1)_____________________________; ?_converse(a,n,m+n-1)_____________________________; }

五、算法设计

下面两题的数据类型定义和函数首部均已给出，请按要求完成算法设计。 １．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子结点的个数。 typedef struct Tnode{

TelemType data;//结点数据域

struct Tnode *firstchild *nextsibling;//指向长子和右兄弟的指针 }CSnode,*CStree;

void leafcount(CStree T , int *count)

{ // 统计以孩子—兄弟链表存储表示的树T的叶子结点数目，结果存于count 所指单元 ，// T

为指向根结点的指针

if(!T->firstchild&&!T->nextsibling) count++; if(T->firstchild) leafcount(T->firstchild, count); if(T->nextsibling) leafcount(T->nextsibling, count); } //leafcout

// binsearch

五、算法设计

下面两题的数据类型定义和函数首部均已给出，请按要求完成算法设计。 １．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子结点的个数。 typedef struct Tnode{

TelemType data;//结点数据域

struct Tnode *firstchild *nextsibling;//指向长子和右兄弟的指针 }CSnode,*CStree;

void leafcount(CStree T , int *count)

{ // 统计以孩子—兄弟链表存储表示的树T的叶子结点数目，结果存于count 所指单元 ，// T

为指向根结点的指针

if(!T->firstchild&&!T->nextsibling) count++; if(T->firstchild) leafcount(T->firstchild, count); if(T->nextsibling) leafcount(T->nextsibling, count); } //leafcout

// binsearch

本文来源：https://www.bwwdw.com/article/3icx.html