目錄
第一章 緒論
第二章 線性表
線性表常用操作辨析總結(jié)
第三章 棧和隊(duì)列
第四章 串
第五章 數(shù)組與廣義表
第六章 樹(shù)
第一章 緒論
1.結(jié)構(gòu)體成員的類(lèi)型必須是基本數(shù)據(jù)類(lèi)型。（F）
原因：結(jié)構(gòu)體成員類(lèi)型不只是基本數(shù)據(jù)類(lèi)型，同時(shí)也可以是另一種結(jié)構(gòu)體類(lèi)型，也可以是指針類(lèi)型，同時(shí)也可以為數(shù)組。（數(shù)組，結(jié)構(gòu)體，共用體，枚舉，指針都可以為成員，但是他們都不是基本數(shù)據(jù)類(lèi)型）
而基本數(shù)據(jù)類(lèi)型是指int，double等
2.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（F）
原因：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位
3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。(F)
原因：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的關(guān)系，而不是數(shù)據(jù)內(nèi)部的各數(shù)據(jù)項(xiàng)之間的關(guān)系。
4.?數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)。（F）?
原因：數(shù)據(jù)的邏輯結(jié)構(gòu)，是數(shù)據(jù)之間的關(guān)系，和存儲(chǔ)結(jié)構(gòu)即物理結(jié)構(gòu)之間沒(méi)有直接的關(guān)系
第二章 線性表
5.線性表中的所有數(shù)據(jù)元素的數(shù)據(jù)類(lèi)型必須相同。（T）
原因：線性表中所有元素具有相同性質(zhì)，在設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)時(shí)，它們對(duì)應(yīng)的數(shù)據(jù)類(lèi)型也必然相同。
數(shù)據(jù)類(lèi)型：是一個(gè)值的集合和定義在該值上的一組操作的總稱
6.可以用帶表頭附加結(jié)點(diǎn)的鏈表表示線性表，也可以用不帶頭結(jié)點(diǎn)的鏈表表示線性表，前者最主要的好處是（B）。
A.可以加快對(duì)表的遍歷
B.使空表和非空表的處理統(tǒng)一
C.節(jié)省存儲(chǔ)空間
D.可以提高存取表元素的速度
?7.下面哪個(gè)不是線性表（D）
A.循環(huán)鏈表
B.隊(duì)列
C.雙向鏈表
D.關(guān)聯(lián)數(shù)組
解析：關(guān)聯(lián)數(shù)組(Associative Array),又稱映射(Map)、字典( Dictionary)是一個(gè)抽象的數(shù)據(jù)結(jié)構(gòu),它包含著類(lèi)似于(鍵,值)的有序?qū)Α?不是線性表。
線性表常用操作辨析總結(jié)
8.某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用什么存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間？（B）
A.單鏈表? B.僅有尾指針的單循環(huán)鏈表? C.僅有頭指針的單循環(huán)鏈表? D.雙鏈表
解析：?鏈表特點(diǎn)，插入刪除方便，修改指針即可。但注意，在最后一個(gè)元素插入刪除，有順序表就選順序表，沒(méi)有順序表，選鏈表就選帶尾指針的，因?yàn)殒湵硪残枰獜念^結(jié)點(diǎn)遍歷到尾節(jié)點(diǎn)，因此帶尾指針的單循環(huán)鏈表最省時(shí)間。
9.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在表尾進(jìn)行插入和刪除運(yùn)算，則利用（ A）存儲(chǔ)方式最節(jié)省時(shí)間。
? A．順序表 ? ? ? ? ? ? ? B．雙向鏈表? ? ? ? C．帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表? ? ? ?D．單循環(huán)鏈表
?解析：題目中說(shuō)，存取任一指定序號(hào)的元素。注意順序表的特性，隨機(jī)存取。另外在表尾刪除，順序表最后一個(gè)元素刪除不需要移動(dòng)元素。
10.設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用(? D? )最節(jié)省時(shí)間。
? A. 單鏈表 ? ? ? ? ? ? ?B.單循環(huán)鏈表? ? ?C. 帶尾指針的單循環(huán)鏈表 ? D. 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表
解析：鏈表操作，末尾插入刪除，選擇帶尾指針的單循環(huán)鏈表的話，插入操作得遍歷一遍；選擇帶頭結(jié)點(diǎn)的雙循環(huán)鏈表，前后都能到達(dá)，時(shí)間復(fù)雜度O(1).?
填空：
#include <stdio.h>
#include <malloc.h>
typedef struct node
{
int data;
struct node *next;
}Snode,*ptr;
void insert(ptr h,int x)//將x插入在表頭位置，即監(jiān)督元之后
{
ptr p;
p=(ptr)malloc(sizeof(Snode));
p->data=x;
p->next=h->next;
h->next=p;
}
void output(ptr h)//輸出鏈表中的元素,即輸出除監(jiān)督元以外的所有元素
{
ptr p;
p=h->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
void del(ptr h)//刪除表頭元素，即監(jiān)督元后第一個(gè)元素結(jié)點(diǎn)
{
ptr p;
p=h->next;
h->next=p->next;
free(p);
}
int main()
{
ptr head;
int x;
head=(ptr)malloc(sizeof(Snode));
head->next=NULL;
scanf("%d",&x);
while(x!=0)
{
insert(head,x);
scanf("%d",&x);
}
output(head);
del(head);
output(head);
return 0;
}11.在下列關(guān)于線性表的敘述中正確的是（D）。
A.線性表的邏輯順序與物理順序總是一致的
B.線性表的順序存儲(chǔ)表示優(yōu)于鏈?zhǔn)酱鎯?chǔ)表示
C.線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有存儲(chǔ)單元的地址可連續(xù)可不連續(xù)
D.除數(shù)組外，每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備3種基本運(yùn)算：插入、刪除和査找
第三章 棧和隊(duì)列
12.令P代表入棧，O代表出棧。若利用堆棧將中綴表達(dá)式3*2+8/4轉(zhuǎn)為后綴表達(dá)式，則相應(yīng)的堆棧操作序列是：C
A.PPPOOO? B.POPOPO? C.POPPOO? D.PPOOPO
解析：將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的過(guò)程如下：（1）如果遇到空格，則認(rèn)為是分隔符，不需要處理。（2）若遇到運(yùn)算數(shù)，則直接輸出（3）若是左括號(hào)，則將其壓入棧中。（4）若遇到右括號(hào)，表明括號(hào)內(nèi)的中極表達(dá)式已經(jīng)掃描完畢，將棧頂?shù)脑貜棾霾⑤敵?，直到遇到左括?hào)為（5）若遇到的是運(yùn)算符，該運(yùn)算符的優(yōu)先級(jí)大于棧頂運(yùn)算符的優(yōu)先級(jí)時(shí)，則把它壓入棧中；該運(yùn)算符的優(yōu)先級(jí)小于等于棧頂運(yùn)算符時(shí)，則將棧頂運(yùn)算符彈出并輸出。
所以該題，一開(kāi)始遇到‘*’，先將‘*’入棧，遇到‘+’，彈出棧頂運(yùn)算符，遇到‘/’，將‘/’入棧，然后再出棧所以是POPPOO
13、若采用帶頭、尾指針的單向鏈表表示一個(gè)堆棧，那么該堆棧的棧頂指針top應(yīng)該如何設(shè)置？A
A.將鏈表頭設(shè)為top
B.將鏈表尾設(shè)為top
C.隨便哪端作為top都可以
D.鏈表頭、尾都不適合作為top
解析：因?yàn)槭菃蜗蜴湵?，如果表尾設(shè)為top，每次刪除都是O(N)的時(shí)間復(fù)雜度，而表頭設(shè)為top就是O(1)。
第四章 串
14.Among the following assignments or initializations, A__ is wrong.
A.char str[10]; str="string";
B.char str[]="string";
C.char *p="string";
D.char *p; p="string";
解析：str是一個(gè)指針常量，它是不能被賦值的也不能進(jìn)行自增自減的！char *p；是定義的一個(gè)指針變量，它指向一個(gè)字符型數(shù)據(jù)，它是可以被賦值的。指針變量和普通變量是一個(gè)道理的，不同的只是指針變量存放的是地址，而普通變量存放的是數(shù)值或字符等。
?15.假設(shè)scanf語(yǔ)句執(zhí)行時(shí)輸入ABCDE<回車(chē)>，能使puts(s)語(yǔ)句正確輸出ABCDE字符串的程序段是( D)。
A.char s[5]={“ABCDE”}; puts(s);
B.char s[5]={‘A’, ‘B’, ‘C’, ‘D’, ‘E’}; puts(s);
C.char *s; scanf("%s", s); puts(s);
D.char *s; s=“ABCDE”; puts(s);
解析：要正常輸出ABCDE必須在字符串的末尾有’\0’作為結(jié)束，這樣輸出函數(shù)才知道什么時(shí)候終止。
A選項(xiàng)中字符串?dāng)?shù)組大小為5只能放ABCDE，放不下’\0’了。如果大小為6，會(huì)自動(dòng)在后面補(bǔ)’\0’
B選項(xiàng)與A一樣，放不下’\0’
C選項(xiàng)，樓主要知道，字符串讀入進(jìn)來(lái)是要存起來(lái)的，而s只是個(gè)指針，存不下這么多字符。必須是char s[6];scanf("%s",s);puts(s);
D選項(xiàng)是正確的，"ABCDE"作為靜態(tài)常量存儲(chǔ)于程序段，地址賦給s，可以正常輸出。
16.若串S="software"，其子串的數(shù)目是（B）
A.8? ?B.37? C.36? D.9
長(zhǎng)為0的子串：1
長(zhǎng)為1的子串：8
長(zhǎng)為2的子串：7
長(zhǎng)為3的子串：6
長(zhǎng)為4的子串：5
長(zhǎng)為5的子串：4
長(zhǎng)為6的子串：3
長(zhǎng)為7的子串：2
長(zhǎng)為8的子串：1
? ? 總和為37
17.串的長(zhǎng)度是指( B)
A.串中所含不同字母的個(gè)數(shù)
B.串中所含字符的個(gè)數(shù)
C.串中所含不同字符的個(gè)數(shù)
D.串中所含非空格字符的個(gè)數(shù)
解釋：串中字符的數(shù)目稱為串的長(zhǎng)度。
第五章 數(shù)組與廣義表
18.一個(gè)廣義表為 ( a, (b, c), d, (), ((f, g), h) )，則該廣義表的長(zhǎng)度與深度分別為（D）。
A.4和6? ? B.6和3? C.3和5? D.5和3
解析：長(zhǎng)度為5：a,(b,c),d,(),((f,g),h))。深度為3：所含括號(hào)的層數(shù)
19.數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)（B ）。
A.55? B.45? C.36? D.16
解析：三維數(shù)組，0——4，共5頁(yè)，-1——-3，3行，5——7列，共5*3*3=45個(gè)元素
20.設(shè)二維數(shù)組A[1… m,1… n]按行存儲(chǔ)在數(shù)組B中，則二維數(shù)組元素A[i,j]在一維數(shù)組B[1…m*n]中的下標(biāo)為 ( A)。
A.n*(i-1)+j? B.n*(i-1)+j-1? C.i*(j-1)? D.j*m+i-1
解析：計(jì)算前i一1行的個(gè)數(shù)，每行有n列，所以個(gè)數(shù)為(i一1)×n，再加上第i行的j個(gè)元素，就像A[2,3]，先求出第二行之前，也就是第一行有多少個(gè)數(shù)，再加上第二行的第三個(gè)就是自己的下標(biāo)了。
21.已知一個(gè)長(zhǎng)度為16的順序表L，其元素按關(guān)鍵字有序排列。若采用二分查找法查找一個(gè)L中不存在的元素，則關(guān)鍵字的比較次數(shù)最多是：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-772347.html
A.4? B.5? C.6? D.7
解析：二分查找的最大比較次數(shù)是?
即[log(N)](向下取整）+1=4+1=5文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-772347.html
第六章 樹(shù)
//創(chuàng)建二叉排序樹(shù)
#include<iostream>
using namespace std;
typedef struct ElemType{
int key;
}ElemType;
int flag=1;
typedef struct BSTNode{
ElemType data;
BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
void InsertBST(BSTree &T,ElemType e ) {
if(!T) {
BSTree S = new BSTNode;
S->data =e;
S->lchild = S->rchild = NULL;
T=S;//填空
}
else if (e.key< T->data.key)
InsertBST(T->lchild,e);//填空
else if (e.key> T->data.key)
InsertBST(T->rchild,e);//填空
}
void CreateBST(BSTree &T ) {
int i=1,n;
cin >> n;
T=NULL;
ElemType e;
while(i<=n){
cin>>e.key;
InsertBST(T, e);
i++;
}
}
void InOrderTraverse(BSTree &T)
{
if(T)
{
InOrderTraverse(T->lchild);
if(flag){cout<<T->data.key;flag=0;}
else cout<<" "<<T->data.key;
InOrderTraverse(T->rchild);
}
}
int main()
{
BSTree T;
CreateBST(T);
InOrderTraverse(T);
return 0;
}到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)（期末總復(fù)習(xí)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
