題數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題ch

1、Ch4棧和隊列（共12題，其中5道算法設(shè)計題）一、選擇題1、設(shè)鏈式棧中結(jié)點的結(jié)構(gòu)為（data, link），且top是指向棧頂?shù)闹羔槨Ｈ粝朐阪準綏５臈ｍ敳迦胍粋€由指針s所指的結(jié)點，則應(yīng)執(zhí)行下列哪一個操作？ （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、設(shè)鏈式棧中結(jié)點的結(jié)構(gòu)為（data, link），且top是指向棧頂?shù)闹羔?。若想摘除鏈式棧的棧?/p>

2、結(jié)點，并將被摘除結(jié)點的值保存到x中，則應(yīng)執(zhí)行下列哪一個操作？（1） 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、設(shè)循環(huán)隊列的結(jié)構(gòu)是const int MaxSize = 100；typedef int DataType；typedef struct DataType dataMaxSize； int front, rear； Queue； 若有一個Queue類型的

3、隊列Q，試問判斷隊列滿的條件應(yīng)是下列哪一個語句？ （1） Q.front = Q.rear； （2）Q.front - Q.rear = MaxSize；（3） Q.front + Q.rear = MaxSize；（4） Q.front = （Q.rear+1） % MaxSize；Key：（4）4、設(shè)循環(huán)隊列的結(jié)構(gòu)是const int MaxSize = 100；typedef int DataType；typedef struct DataType dataMaxSize； int front，rear； Queue；若有一個Queue類型的隊列Q，試問應(yīng)用下列哪一個語句計算隊列元素個數(shù)

4、？（1）（Q.rear - Q.front + MaxSize ） % MaxSize；（2） Q.rear - Q.front +1；（3）Q.rear - Q.front -1； （4） Q.rear - Qfront；Key：（1）二、簡答題5、試回答下列問題：（1） 設(shè)整數(shù)1, 2, 3, 4, 5, 6依次進棧，則可能的出棧序列有多少種?（2） 若整數(shù)1, 2, 3, 4, 5, 6依次進棧，那么是否能夠得到435612, 325641, 154623和135426的出棧序列。Key：1）可能的不同的出棧序列有 =132種？2）不能得到435612，154623這樣的出棧序列。因為若

5、在4，3，5，6之后再將1，2出棧，則1，2必須一直在棧中，此時1先進棧，2后進棧，2應(yīng)壓在1上面，不能1先于2出棧。154623同理。出棧序列325641，135426可以得到。6、設(shè)有一個順序棧S，元素s1, s2, s3, s4, s5, s6依次進棧，如果6個元素的出棧順序為s2, s3, s4, s6, s5, s1，則順序棧的容量至少應(yīng)為多少？Key：37、假設(shè)以數(shù)組Qm存放循環(huán)隊列中的元素, 同時以rear和length分別指示循環(huán)隊列中的隊尾位置和隊列中所含元素的個數(shù)。試給出該循環(huán)隊列的隊空條件和隊滿條件, 并寫出相應(yīng)的插入（EnQueue）和刪除（DlQueue）元素的操作。

6、三、算法設(shè)計題8、設(shè)順序棧S的元素個數(shù)最大為MaxSize。試改寫順序棧的進棧函數(shù)Push （S, x），要求當棧滿時執(zhí)行一個stackFull（S） 操作進行棧滿處理。其功能是：動態(tài)創(chuàng)建一個比原來的棧元素存放數(shù)組大二倍的新數(shù)組，代替原來的棧元素存放數(shù)組，原來棧元素存放數(shù)組中的元素占據(jù)新數(shù)組的前MaxSize位置。Key：typedef structelemtype *elements；inttop；int maxsize； stack；void Push（stack *s,elemtype x）if（s->top = s->maxsize -1）stackFull（s）；s-&g

7、t;top =s->top+1；*（s->elements+s->top） =x；void stackFull（stack *s）int i；elemtype *temp；temp =（elemtype *）malloc（sizeof（elemtype） * （s->maxsize） *3）；for（i=0；i<= s->top；i+）*（temp+i）= *（s->elements+i）；s->maxsize *= 3；s->elements = temp；9、假設(shè)以數(shù)組Qm存放循環(huán)隊列中的元素, 同時設(shè)置一個標志tag，以tag = 0

8、和tag = 1來區(qū)別在隊頭指針（front）和隊尾指針（rear）相等時，隊列狀態(tài)為“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入（EnQueue）和刪除（DeQueue）的函數(shù)。Key：typedef structint 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"

9、）；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、若使用循環(huán)鏈表來表示隊列，p是鏈表中的一個指針（視為隊尾指針）。試基于此結(jié)構(gòu)給出隊列的插入（EnQueue）和刪除（DeQueue）的函數(shù)，并給出p為何值時隊列空。Key：12、