第一章 绪论

一．选择题

1．数据结构被形式地定义为（K，R），其中K是①_B_的有限集合，R是K上的②_D_的有限集合。

①A．算法 B．数据元素 C．数据操作 D．逻辑结构

②A．操作 B．映象 C．存储 D．关系

2．算法分析的目的是①C，算法分析的两个主要方面是②A。

3． 在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为(B)

A．逻辑结构 　　B．顺序存储结构

C．链表存储结构 　D．以上都不对

4．数据结构中，在逻辑上可以把数据结构分成：( C ）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构

C．线性结构和非线性结构 D．内部结构和外部结构

5．以下属于顺序存储结构优点的是（ A ）。

A．存储密度大 B．插入运算方便

C．删除运算方便 　　D．可方便地用于各种逻辑结构的存储表示

6．数据结构研究的内容是（ D ）。

A．数据的逻辑结构 B．数据的存储结构

C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面

7．链式存储的存储结构所占存储空间（A ）。

A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

B．只有一部分，存放结点值

C．只有一部分，存储表示结点间关系的指针

D．分两部分，一部分存放结点值，另一部分存放结点所占单元数

8．一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（ A ）。

A．确定性、可行性、有穷性 B．易读性、确定性、有效性

C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性

9．以下关于数据的逻辑结构的叙述中正确的是（ A）。

A．数据的逻辑结构是数据间关系的描述

B．数据的逻辑结构反映了数据在计算机中的存储方式

C．数据的逻辑结构分为顺序结构和链式结构

D．数据的逻辑结构分为静态结构和动态结构

10．算法分析的主要任务是（ C ）。

A．探讨算法的正确性和可读性 B．探讨数据组织方式的合理性

C．为给定问题寻找一种性能良好的解决方案 D．研究数据之间的逻辑关系

二．解答

设有一数据的逻辑结构为：B=(D, S)，其中：

D={d1, d2, …, d9}

S={, , , , , , , , , , }画出这个逻辑结构示意图。

d1 d8 d3 d2 d4 d5 d9 d7 d6

第二章 线性表

一、选择题

1．下述哪一条是顺序存储结构的优点？（ A）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

2．下面关于线性表的叙述中，错误的是哪一个？（ B）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

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

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表

5．在一个长度为n的顺序表中删除第i个元素(0next->next; B．p=p->next;

C．p=p->next->next; D．p->next=p;

8．在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（B）

A．s->next=p->next; p->next=s

B．q->next=s; s->next=p

C．p->next=s->next; s->next=p

D．p->next=s; s->next=q

9．线性表的顺序存储结构是一种（A）的存储结构。

A．随机存取 B．顺序存取 C．索引存取 D．散列存取

二、填空

1．在线性表的顺序存储中，元素之间的逻辑关系是通过 物理位置相邻 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 指针 决定的。

2．在双向链表中，每个结点含有两个指针域，一个指向 .直接前驱 结点，另一个指向 直接后继 结点。

3．当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_顺序 存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用 链式 存储结构为宜。

三、算法设计

1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法（要求用最少的时间和最小的空间）

①确定在序列中比正整数x大的数有几个（相同的数只计算一次）

②将单链表中比正整数x小的偶数从单链表中删除

int count(Linklist h,int x)

{

int num=0;

Linknode *p;

p=h->next;

while(p&&p->datanext;

while§

if(p->next&&p->data==p->next->data)

//若p没有指向链表中同一数值的最后一个结点，则向后移动

//若p指向数值相同的结点中的最后一个，则num加1，p指针后移，继续执行while循环

return num;

}

②

void delevenl(Linklist &h,int x)

{

Linknode *p,*r;

p=h->next;r=h;

while(p&&p->data

p->next=h;

h=p;

}

3．设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。

3．void decompose(Linklist La,Linklist &Lb,Linklist &Lc)

{

}

4．int subset(LinkList la, LinkList lb)

{ LinkNode * pa,*pb;

pa=la->next;

while(pa)

{ pb=lb->next;

return 1;

}算法时间复杂度O（A.Length*B.Length）

5．设有一单循环链表la，其结点有三个域：prior、data与next，其中data为数据域,，next域指向直接后继，prior域应指向直接前驱，但目前空着。试写一算法将此单循环链表改造为双向循环链表。

5．void priorset(DuLinkList &la)

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

while(q!=la){q->prior=p; p=q;q=q->next;}

q->prior=p;

}

第三章 栈和队列

一、选择题

1．设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列（C ）

A．A, B, C, D, E B．B, C, D, E, A

C．E, A, B, C, D D．E, D, C, B, A

2．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（C ）

A．top不变 B．top=0 C．top-- D．top++

3．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（ D）

A．rear％n= = front B．（front+l）％n= = rear

C．rear％n -1= = front D．(rear+l)％n= = front

4．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（ C）

A．rear％n= = front B．front+l= rear

C．rear= = front D．(rear+l)％n= front

5．在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ A）

A．front=front->next 　 B．rear=rear->next

C．rear=front->next 　D．front=rear->next

6．某堆栈的输入序列为1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为（ C）

A．i B．n-i C．n-i+1 D．哪个元素无所谓

二、解答题

1．一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。

1．双向栈

栈底1 ……….

………

栈底2 //双向栈类型定义

#define STACK_SIZE 100;

Typedef struct {

Status InitStack ( SqStack &S) {

//初始化双向栈

S.base_one=S.top_one=( SElemType *)malloc(STACK_SIZE * sizeof(SElemType));//第一个栈底和栈顶指向数组起点

S.base_two=S.top_two=S.base_one +STACK_SIZE-1;// 第二个栈底和栈顶指向数组终点

S.stacksize= STACK_SIZE ;

return OK;

}//InitStack

Status Push ( SqStack &S, int i, SElemType e){

//入栈操作，i=0时将e存入前栈，i=1时将e存入后栈

if( S.top_two < S.top_one) return OVERFLOW;//栈满，不考虑追加空间

if( i = = 0 )

*S.top_one++ = e;

else

*S.top_two-- = e;

return OK;

}//Push

SElemType Pop ( SqStack &S, int i){

//出栈操作，i=0出前栈，i=1出后栈

if( i==0 ) {

else {

return e;

}//Pop

2．利用两个栈S1、S2模拟一个队列时，如何使用栈的运输实现队列的插入、删除运算。

2．#define M 3

struct Stack{

};

struct Queue{

};

void InitQueue(Queue &Q)//初始化队列

{

}

int IsEmpty(Queue &Q)//判断队列是否为空

{

}

int IsFull(Queue &Q)

{

}

void InQueue(Queue &Q,Qelemtype e)

{

};

struct LinkQueue

{

};

void InitQueue(LinkQueue &Q) //置空队

{

}

int EmptyQueue(LinkQueue Q) //判队空

{

}

void EnQueue(LinkQueue &Q, Qelemtype e)//元素入队

{

//新建一个结点，并置其值为e

//将结点插入队列末尾

//修改队尾指针

}

void DeQueue(LinkQueue &Q,Qelemtype &e) //元素出队

{

char data[10];

int top;

}stack;

int descion(char *str)

{

stack s;

int i;

s.top=0;

for(i=0;str[i];i++)

{

switch(str[i])

{

}

}

if(s.top==0) return 1;

else return 0;

}

第四章 串

一．选择题

A.连接　　 B.模式匹配 　　C.求串长　　 D .求子串

2．设字符串 S1=“ABCDEFG”，S2=“PQRST”，则运算：

S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为 （　D）

A．A BCDEF 　　B．BCDEFG 　　C．BCDPQRST 　D． BCDEFEF

A.串是一种特殊的线性表 B. 串的长度必须大于零

C.串中元素只能是字母 D. 空串就是空白串

A.两串的长度相等

B.两串包含的字符相同

C.两串的长度相等，并且两串包含的字符相同

D.两串的长度相等，并且对应位置上的字符相同

二、填空题

2.空格串的长度为 ．空格数 ，空串的长度为 0 。

3.设串S=’How are you’，则串的长度为 11 。

三、问答题

回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符变量是否为回文。

Status IsHuiwen( char *S)

{ i=0;

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

i=i-1; j=0;

while(j0）的满二叉树对应森林的由 棵树构成。

三．已知一个二叉树的中序序列为CBEDAHGIJF,后序序列为CEDBHJIGFA。

1．画出该二叉树。

2．画出该二叉树的先序线索二叉树。

四．试找出分别满足下列条件的所有二叉树：

1．先序序列和中序序列相同。

2．中序序列和后序序列相同。

3．先序序列和后序序列相同。

五、设二叉树用二叉链表表示，设计算法求二叉树的高度。

int Depth(BiTree t)（后序遍历）

{ if(！t)

{dl=Depth(t->lchild);

return d;

}

六、设T是一棵具有n个结点的二叉树，若给定二叉树T的先序序列和中序序列，并假设T的先序序列和中序序列分别放在数组PreOrder[1…n]和InIrder[1…n]中，设计一个构造二叉树T的二叉链表存储结构的算法。

六 //根据二叉树的先序序列和中序序列创建二叉链表

void createBiTree(char pre[],char in[],int start,int end,int &count,BiTree &T)

//按先序次序创建二叉链表，pre为存放先序序列的字符数组，in为存放中序序列的字符数组，

//count为二叉树的根结点在先序序列中的序号

//start和end为以pre[count]为根的二叉树在中序序列中的起始位置和结束位置

//T为二叉链表的根指针，

{

for(int i=0;in[i]!=’\0’;i++) //查找根结点在中序序列in[ ]中的下标

if(in[i]==pre[count]) break;

count++;

if(in[i]==’\0’) cout