实用数据结构基础参考答案 下载本文

top=top–M; } } }

(2)设计一个算法,要求判别一个算术表达式中的圆括号配对是否正确。 解://设表达式在字符数组a[ ]中,使用一堆栈S来帮助判断。 int correct (char a[ ]) {

stack s ;

InitStack (s); //调用初始化栈函数 for (i=0; i

if (a[i]= =’)’) {

if StackEmpty (s) //调用判栈空函数

return 0; //若栈为空返回0;否则出栈 else

Pop(s); }

if (StackEmpty (s) ) //调用判栈空函数 printf (“配对正确!”); //若栈空,说明配对正确,并返回1 else

printf (“配对错误!”); //配对错误返回0 }

(3) 设计一个将十进正整数转换为十进制数的算法,并要求上机调试通过。 解: #include #include

typedef struct stacknode { int data;

struct stacknode *next; }stacknode; typedef struct {

stacknode *top;

//定义栈顶的指针

//栈的应用:十——十六进制转换

}linkstack;

void Conversion(int n) { linkstack s; int x;

s.top=NULL; do

17

//定义栈的存储结构

//置栈空

{ x=n; //取余数 n= n/16 ; //取新的商 stacknode *p=new stacknode; //申请新结点 p->next=s.top ; //修改栈顶指针 s.top=p; s.top->data=x; //余数入栈 }

while(n);

printf(\转换后的十六进制数值为:\

while (s.top) { if(s.top->data<10);

printf(\ else

switch(s.top->data) {

case 10: printf(\case 11: printf(\case 12: printf(\case 13: printf(\case 14: printf(\case 15: printf(\}

stacknode *p=s.top;

s.top=s.top->next; free(p) ; }

printf(\}

void main() {

int n;

printf(\请输入一个十进制正整数:\scanf(\Conversion(n); }

18

//出栈处理 //出栈一个余数,收回一个结 单元练习4

一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳ )

(√)(1)队列是限制在两端进行操作的线性表。

(√)(2)判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。 (×)(3)在链队列上做出队操作时,会改变front指针的值。

(√)(4)在循环队列中,若尾指针rear大于头指针front,其元素个数为rear- front。 (×)(5)在单向循环链表中,若头指针为h,那么p所指结点为尾结点的条件是p=h。 (√)(6)链队列在一定范围内不会出现队满的情况。 (×)(7)在循环链队列中无溢出现象。 (×)(8)栈和队列都是顺序存储的线性结构。 (×)(9)在队列中允许删除的一端称为队尾。

(×)(10)顺序队和循环队关于队满和队空的判断条件是一样的。

二.填空题

(1) 在队列中存取数据应遵循的原则是 先进先出 。

(2) 队列 是被限定为只能在表的一端进行插入运算,在表的另一端进行删

除运算的线性表。

(3) 在队列中,允许插入的一端称为 队尾 。

(4) 在队列中,允许删除的一端称为 队首(或队头) 。 (5) 队列在进行出队操作时,首先要判断队列是否为 空 。 (6) 顺序队列在进行入队操作时,首先要判断队列是否为 满 。 (7) 顺序队列初始化后,front=rear= -1 。 (8) 解决顺序队列“假溢出”的方法是采用 循环队列 。

(9) 循环队列的队首指针为front,队尾指针为rear,则队空的条件为 front ==

rear 。

(10) 链队列LQ为空时,LQ->front->next= NULL 。

(11) 设长度为n的链队列用单循环链表表示,若只设头指针,则入队操作的时间

复杂度为 O(n)。

(12) 设长度为n的链队列用单循环链表表示,若只设尾指针,则出队操作的时间

复杂度为 0(1) 。

(13) 在一个链队列中,若队首指针与队尾指针的值相同,则表示该队列为

空 。

(14) 设循环队列的头指针front指向队首元素,尾指针rear指向队尾元素后的一

个空闲元素,队列的最大空间为MAXLEN,则队满标志为: front==(rear+1)%MAXLEN 。

(15) 在一个链队列中,若队首指针为front,队尾指针为rear,则判断该队列只

有一个结点的条件为: front==rear && front !NULL 。

19

( 或 front==rear && front <>NULL )

(16) 向一个循环队列中插入元素时,首先要判断 队尾指针 ,然后再向指

针所指的位置写入新的数据。

(17) 读队首元素的操作 不改变(或不影响) 队列元素的个数。

(18)设循环队列的容量为40(序号从0到39),现经过一系列的入队和出队运算后,有 front=11,rear=19,则循环队列中还有 8 个元素。

(L= (N+rear-front)% N=(40+19-11)% 40=8)

(19)队列Q,经过下列运算:InitQueue(Q)(初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是 0 。 (20)队列Q经过InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b); ReadFront(Q,x)后,x的值是 a 。

三.选择题

(1)队列是限定在( D )进行操作的线性表。 A.中间 A.不变的

B.队首 B.可变的

C.队尾 C.任意的

D.端点 D.0 D.不限制 D.非

(2)队列中的元素个数是( B )。 (3)同一队列内各元素的类型( A )。 A.必须一致

B.不能一致 C.可以不一致

(4)队列是一个( C )线性表结构。

A.不加限制的 B.推广了的 C.加了限制的 ( B )。 A.n-2

B.n-1

C.n D.n+1 C.不能固定 D.动态变化

C.不能连续 D.可以不连续

(6)一个循环队列一旦说明,其占用空间的大小( A )。 A.已固定 B.可以变动 (7)循环队列占用的空间( A )。 A.必须连续 ( B )。

A.0..10 B.0..9 A.B,C,D,A C.A,B,C,D A. A C. C

C.1..9 D.1..10 B.A,C,B,D D.C,B,D,A

B. B

D. D

(9)若进队的序列为:A,B,C,D,则出队的序列是( C )。

B.不必连续

(8)存放循环队列元素的数组data有10个元素,则data数组的下标范围是(5)当利用大小为n的数组顺序存储一个队列时,该队列的最后一个元素的下标为

(10)四个元素按:A,B,C,D顺序连续进队Q,则队尾元素是( D )。

(11)四个元素按:A,B,C,D顺序连续进队Q,执行一次OutQueue(Q)操作后,队

20