题数据结构复习题_ch

1、Ch4栈和队列（共12题，其中5道算法设计题）一、选择题1、设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行下列哪一个操作？ （1） top-link = s；（2） s-link = top-link； top-link = s；（3） s-link = top； top = s； （4） s-link = top； top = top-link；Key：（3）2、设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列哪一个操

2、作？x= top-data； top = top-link；（2） top = top-link； x = top-data；（3） x = top； top = top-link；（4） x = top-data；Key：（1）3、设循环队列的结构是const int MaxSize = 100；typedef int DataType；typedef struct DataType dataMaxSize； int front, rear； Queue； 若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句？ （1） Q.front = Q.rear； （2）Q.fron

3、t - Q.rear = MaxSize；（3） Q.front + Q.rear = MaxSize；（4） Q.front = （Q.rear+1） % MaxSize；Key：（4）4、设循环队列的结构是const int MaxSize = 100；typedef int DataType；typedef struct DataType dataMaxSize； int front，rear； Queue；若有一个Queue类型的队列Q，试问应用下列哪一个语句计算队列元素个数？（1）（Q.rear - Q.front + MaxSize ） % MaxSize；（2） Q.rear -

4、 Q.front +1；（3）Q.rear - Q.front -1； （4） Q.rear - Qfront；Key：（1）二、简答题5、试回答下列问题：（1） 设整数1, 2, 3, 4, 5, 6依次进栈，则可能的出栈序列有多少种?（2） 若整数1, 2, 3, 4, 5, 6依次进栈，那么是否能够得到435612, 325641, 154623和135426的出栈序列。Key：1）可能的不同的出栈序列有 =132种？2）不能得到435612，154623这样的出栈序列。因为若在4，3，5，6之后再将1，2出栈，则1，2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不能1先于2

5、出栈。154623同理。出栈序列325641，135426可以得到。6、设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？Key：37、假设以数组Qm存放循环队列中的元素, 同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入（EnQueue）和删除（DlQueue）元素的操作。三、算法设计题8、设顺序栈S的元素个数最大为MaxSize。试改写顺序栈的进栈函数Push （S, x），要求当

6、栈满时执行一个stackFull（S） 操作进行栈满处理。其功能是：动态创建一个比原来的栈元素存放数组大二倍的新数组，代替原来的栈元素存放数组，原来栈元素存放数组中的元素占据新数组的前MaxSize位置。Key：typedef structelemtype *elements；inttop；int maxsize； stack；void Push（stack *s,elemtype x）if（s-top = s-maxsize -1）stackFull（s）；s-top =s-top+1；*（s-elements+s-top） =x；void stackFull（stack *s）int i；

7、elemtype *temp；temp =（elemtype *）malloc（sizeof（elemtype） * （s-maxsize） *3）；for（i=0；itop；i+）*（temp+i）= *（s-elements+i）；s-maxsize *= 3；s-elements = temp；9、假设以数组Qm存放循环队列中的元素, 同时设置一个标志tag，以tag = 0和tag = 1来区别在队头指针（front）和队尾指针（rear）相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入（EnQueue）和删除（DeQueue）的函数。Key：typedef structi

8、nt front,rear,tag；/队头指针，队尾指针，队满标志elemtype *Q；int maxsize；queue；void EnQueue（queue *q,elemtype x）if（q-front = q-rear & q-tag =1）printf（error,the queue is full!n）；exit（0）；elserear = （rear+1） % （q-maxsize）；/队尾进1，队尾指针表示实际队尾位置*（q-Q+rear） =x；/元素进队列q-tag =1；/标志改1，表示队列不空elemtype DeQueue（queue *q）if（q-front = q-rear & q-tag =0）printf（error,the queue is empty!n）；exit（0）；elsefront = （front+1） % （q-maxsize）；/队头进1，队头指针表示实际队头的前一位置q-tag =0；/标志改0，表示队列不满return *（q-Q+front）；/返回队头元素的值10、若使用循环链表来表示队列，p是链表中的一个指针（视为队尾指针）。试基于此结构给出队列的插入（EnQueue）和删除（DeQueue）的函数，并给出p为何值时队列空。Key：