數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題要點(diǎn)(整理版)-文庫(kù)吧資料
2025-04-23 01:46本頁(yè)面
【正文】 truct list *p。 pnext=head。 p=(struct list *)malloc(LEN)。 return(p)。 p=(struct list *)malloc(LEN)。 return (Q)。 if(==p)==NULL。 =pnext。 p=next。 }出隊(duì)：LinkQueue DeQueue(LinkQueue Q){ int e。 =p。 pnext=NULL。 p=(QueuePtr)malloc(sizeof(QNode))。 return (Q)。創(chuàng)建：LinkQueue InitQueue(LinkQueue Q){ ==(QueuePtr)malloc(sizeof(QNode))。 QueuePtr rear。 }QNode,*QueuePtr。，比較明顯的優(yōu)點(diǎn)是：（D） 考點(diǎn)1：隊(duì)列的編程：結(jié)構(gòu)：typedef struct QNode{ int date。已知鏈棧Q，編寫(xiě)函數(shù)判斷棧空，如果?？談t進(jìn)行入棧操作，否則出棧并輸出。棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出。補(bǔ)充內(nèi)容：一個(gè)棧的入棧序列為“ABCDE”，則以下不可能的出棧序列是（B）A. BCDAE B. EDACB C. BCADE D. AEDCB棧的順序表示中，用TOP表示棧頂元素，那么棧空的條件是（D）A. TOP==STACKSIZE B. TOP==1 C. TOP==0 D. TOP==1允許在一端插入，在另一端刪除的線性表稱(chēng)為隊(duì)列。 //棧頂指針 struct list *base。結(jié)構(gòu)：typedef struct list{ int listsize。若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)采用順序存儲(chǔ)表示較好。 (2) 若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)，應(yīng)采用哪種存儲(chǔ)表示？為什么？應(yīng)采用順序存儲(chǔ)表示。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素原來(lái)的物理順序，只需要保持原來(lái)的邏輯順序，因此不必移動(dòng)數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。同時(shí)，由于在插入或刪除時(shí)，為保持原有次序，平均需要移動(dòng)一半(或近一半)元素，修改效率不高。試問(wèn)：(1) 兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?順序表的存儲(chǔ)效率高，存取速度快。10. 對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的單鏈表 ,在已知所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是(O（1）)；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是（O(n)）。//這種題目靠一根指針是沒(méi)有辦法完成的，必須要借助第二根指針。 pnext=( pnextnext )。C. pnext=pnext D. p=pnextnext5. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較（B ）個(gè)結(jié)點(diǎn)。B. p=pnext。 snext=p。 p=s。 pnext=s。 pnext=s。 return 1。 //修改前趨的后繼指針 delete p。} p=qnext。 //找待刪點(diǎn)的直接前趨 if(q==NULL || qnext==NULL) //即i1或in時(shí) {cout”非法刪除位置!\n”。 //插入成功}：（C語(yǔ)言中需要把head轉(zhuǎn)化為全局變量才能實(shí)現(xiàn)此程序）int delete(lklist head,int i) { pointer p,q。 //新點(diǎn)的后繼是原第i個(gè)點(diǎn) qnext=s。 sdata=x。} s=new node。 //這是C++做法，即C語(yǔ)言中的 printf(“非法插入位置!\n”)。 q=get(head,i1)。 return head。 //循環(huán)鏈表則是headnext=head。//這是C++做法 //head=( pointer)malloc(sizeof(Lnode))。 //單鏈表類(lèi)型，即頭指針類(lèi)型：lklist initlist() { pointer head。 //雙向鏈表還應(yīng)加上*previous} Lnode, * pointer 。 //結(jié)點(diǎn)數(shù)據(jù)類(lèi)型，假設(shè)為inttypedef struct node { //結(jié)點(diǎn)結(jié)構(gòu) datatype data。（第n個(gè)元素的地址即首地址+(n1)*每個(gè)元素的存儲(chǔ)空間，如a[12]（第13個(gè)元素）的地址=a[0]+12*3）設(shè)有一帶頭結(jié)點(diǎn)單鏈表L，請(qǐng)編寫(xiě)該單鏈表的初始化，插入、輸出和刪除函數(shù)。若線性表的主要操作是在最后一個(gè)元素之后插入一個(gè)元素或刪除最后一個(gè)元素，則采用順序表存儲(chǔ)結(jié)構(gòu)最節(jié)省運(yùn)算時(shí)間。 free(q)。補(bǔ)充內(nèi)容：線性表中，第一個(gè)元素沒(méi)有直接前驅(qū)，最后一個(gè)元素沒(méi)有直接后驅(qū)。p。 free(q)。刪除：q=pnext。 headnext=p。（2） 鏈表操作算法：初始化、插入、輸出、刪除、遍
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1