清華數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案(C語(yǔ)言版嚴(yán)蔚敏)
《清華數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案(C語(yǔ)言版嚴(yán)蔚敏)》由會(huì)員分享，可在線閱讀，更多相關(guān)《清華數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案(C語(yǔ)言版嚴(yán)蔚敏)（123頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、 清華數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案 (C 語(yǔ)言版嚴(yán)蔚敏 ) 第 1 章 緒論 1.1 簡(jiǎn)述下列術(shù)語(yǔ)：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。 解：數(shù)據(jù) 是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。 數(shù)據(jù)元素 是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。 數(shù)據(jù)對(duì)象 是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 數(shù)據(jù)結(jié)構(gòu) 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 存儲(chǔ)結(jié)構(gòu) 是數(shù)據(jù)
2、結(jié)構(gòu)在計(jì)算機(jī)中的表示。 數(shù)據(jù)類型 是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。 抽象數(shù)據(jù)類型 是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。是對(duì)一般數(shù)據(jù)類型的擴(kuò)展。 1.2 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類型概念的區(qū)別。 解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語(yǔ)言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。抽象數(shù)據(jù)類型通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進(jìn)行的操作。在定義抽象數(shù)據(jù)類型中的數(shù)據(jù)部分和操作部分時(shí)，要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作
3、說(shuō)明，不考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的具體實(shí)現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。 1.3 設(shè)有數(shù)據(jù)結(jié)構(gòu) (D,R) ，其中 D d1, d 2, d 3, d 4 ， R r ， r d1, d 2 , d 2,d 3 , d 3, d 4 試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。 解： 1.4 試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復(fù)數(shù)和有理數(shù)的定義（有理數(shù)是其分子、分母均 為自然數(shù)且分母不為零的分?jǐn)?shù)） 。 解： ADT Complex{ 數(shù)據(jù)對(duì)象： D={r,i|r,i 為實(shí)數(shù) }
4、
數(shù)據(jù)關(guān)系： R={
5、數(shù) C的兩個(gè)元素按降序排列，則返回 1，否則返回 0
Max(C,&e)
操作結(jié)果：用 e 返回復(fù)數(shù) C的兩個(gè)元素中值較大的一個(gè)
Min(C,&e)
操作結(jié)果：用 e 返回復(fù)數(shù) C的兩個(gè)元素中值較小的一個(gè)
}ADT Complex
ADT RationalNumber{
數(shù)據(jù)對(duì)象： D={s,m|s,m 為自然數(shù)，且 m不為 0}
數(shù)據(jù)關(guān)系： R={
6、nalNumber(&R) 操作結(jié)果：銷毀有理數(shù) R Get(R,k,&e) 操作結(jié)果：用 e 返回有理數(shù) R 的第 k 元的值 Put(&R,k,e) 操作結(jié)果：改變有理數(shù) R 的第 k 元的值為 e IsAscending(R) 操作結(jié)果：若有理數(shù) R的兩個(gè)元素按升序排列，則返回 1，否則返回 0 IsDescending(R) 操作結(jié)果：若有理數(shù) R的兩個(gè)元素按降序排列，則返回 1，否則返回 0 Max(R,&e) 操作結(jié)果：用 e 返回有理數(shù) R 的兩個(gè)元素中值較大的一個(gè) Min(R,&e) 操作結(jié)果：用 e
7、 返回有理數(shù) R 的兩個(gè)元素中值較小的一個(gè)
}ADT RationalNumber
1.5 試畫出與下列程序段等價(jià)的框圖。
(1) product=1; i=1; while(i<=n){
product *= i; i++;
}
(2) i=0;
do {
i++;
} while((i!=n) && (a[i]!=x));
(3) switch {
case x 8、s(y);
}
1.6 在程序設(shè)計(jì)中，常用下列三種不同的出錯(cuò)處理方式：
(1) 用 exit 語(yǔ)句終止執(zhí)行并報(bào)告錯(cuò)誤；
(2) 以函數(shù)的返回值區(qū)別正確返回或錯(cuò)誤返回；
(3) 設(shè)置一個(gè)整型變量的函數(shù)參數(shù)以區(qū)別正確返回或某種錯(cuò)誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn)。
解： (1)exit 常用于異常錯(cuò)誤處理，它可以強(qiáng)行中斷程序的執(zhí)行，返回操作系統(tǒng)。
(2) 以函數(shù)的返回值判斷正確與否常用于子程序的測(cè)試，便于實(shí)現(xiàn)程序的局部控制。
(3) 用整型函數(shù)進(jìn)行錯(cuò)誤處理的優(yōu)點(diǎn)是可以給出錯(cuò)誤類型，便于迅速確定錯(cuò)誤。
1.7 在程序設(shè)計(jì)中，可采用下列三種 9、方法實(shí)現(xiàn)輸出和輸入：
(1) 通過(guò) scanf 和 printf 語(yǔ)句；
(2) 通過(guò)函數(shù)的參數(shù)顯式傳遞；
(3) 通過(guò)全局變量隱式傳遞。
試討論這三種方法的優(yōu)缺點(diǎn)。
解：(1) 用 scanf 和 printf 直接進(jìn)行輸入輸出的好處是形象、 直觀，但缺點(diǎn)是需要對(duì)其進(jìn)行格式控制，
較為煩瑣，如果出現(xiàn)錯(cuò)誤，則會(huì)引起整個(gè)系統(tǒng)的崩潰。
(2) 通過(guò)函數(shù)的參數(shù)傳遞進(jìn)行輸入輸出，便于實(shí)現(xiàn)信息的隱蔽，減少出錯(cuò)的可能。
(3) 通過(guò)全局變量的隱式傳遞進(jìn)行輸入輸出最為方便， 只需修改變量的值即可， 但過(guò)多的全局變量使程序的維護(hù)較為困難。
1.8 設(shè) 10、n 為正整數(shù)。試確定下列各程序段中前置以記號(hào) @的語(yǔ)句的頻度：
(1) i=1; k=0; while(i<=n-1){
@ k += 10*i; i++;
}
(2) i=1; k=0; do {
@ k += 10*i; i++;
} while(i<=n-1);
(3) i=1; k=0; while (i<=n-1) { i++;
@ k += 10*i;
}
(4) k=0;
for(i=1; i<=n; i++) {
for(j=i; j<=n; j++)
@ k++;
}
(5) for(i=1; i< 11、=n; i++) {
for(j=1; j<=i; j++) {
for(k=1; k<=j; k++)
@ x += delta;
}
(6) i=1; j=0; while(i+j<=n) {
@ if(i>j) j++; else i++;
}
(7) x=n; y=0; // n 是不小于 1 的常數(shù)
while(x>=(y+1)*(y+1)) {
@ y++;
}
(8) x=91; y=100; while(y>0) {
@ if(x>100) { x -= 10; y--; } else x 12、++;
}
解： (1) n-1
(2) n-1
(3) n-1
(4) n+(n-1)+(n-2)+...+1=
n(n
1)
2
(5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=
n i (i
1)
2
i
1
=
1 n
i (i
1)
1 n
(i 2
i )
1 n
i 2
1 13、 n
i
2 i 1
2 i 1
2 i 1
2 i 1
1
1
1
(
1)(2
3)
n(n
1)( 2n
1)
n(n
1)
=
12
4
12
(6) n
(7) n 向下取整
(8) 1100
1.9
假設(shè) n 為 2 的乘冪， 并且 n>2，試求下列算法的時(shí)間復(fù)雜度及變量
int Time(int n) {
count = 14、0; x=2;
while(x 15、
運(yùn)算的時(shí)間為
10 7
秒（100 多天），又每秒可執(zhí)行基本操作 （根據(jù)這些操作來(lái)估算算法時(shí)間復(fù)雜度）
105
次。
試問(wèn)在此條件下，
這兩個(gè)算法可解問(wèn)題的規(guī)模
（即
n 值的范圍） 各為多少？哪個(gè)算法更適宜？請(qǐng)說(shuō)明理由。
解： 2 n
1012
n=40
n10
1012
n=16
則對(duì)于同樣的循環(huán)次數(shù) n，在這個(gè)規(guī)模下，第二種算法所花費(fèi)的代價(jià)要大得多。故在這個(gè)規(guī)模下，第
16、
一種算法更適宜。
1.12 設(shè)有以下三個(gè)函數(shù)：
f n
21 4
n
2
1000 ，
g n 15n
4
500n
3
，
h n 500n
3.5
nlog n
n
請(qǐng)判斷以下斷言正確與否：
(1) f(n) 是 O(g(n))
(2) h(n) 是 O(f(n))
(3) g(n) 是 O(h(n))
(4) h(n) 是 O(n3.5 )
(5) h(n) 是 O(nlogn)
解： (1)
對(duì) (2) 錯(cuò) (3) 錯(cuò) (4)
17、對(duì) (5) 錯(cuò)
1.13
試設(shè)定若干 n 值，比較兩函數(shù)
n 2
和 50n log 2 n的增長(zhǎng)趨勢(shì)，并確定
n 在什么范圍內(nèi)，函數(shù)
n 2
的值
大于 50n log 2 n 的值。
解： n 2
的增長(zhǎng)趨勢(shì)快。但在
n 較小的時(shí)候，
50n log 2 n 的值較大。
當(dāng) n>438 時(shí)， n 2
50n log 2 n
1.14
判斷下列各對(duì)函數(shù) f n 和 g n
，當(dāng) n
時(shí)，哪個(gè)函數(shù)增長(zhǎng)更快？
(1)
f
n
10n 2
ln 18、n!
10n3
， g n
2n4
n 7
(2)
f
n
ln n!
5 2
， g n
13n2.5
(3)
f
n
n2.1
n 4
1 ， g n
ln n! 2
n
(4)
f
n
2 n3
2n 2
， g n
n n 2
n5
解： (1)g(n)
快 (2)g(n)
快 (3)f(n)
快 (4) f(n)
快
1.15 試用數(shù)學(xué)歸納法證明：
n
i 2
1
2n
1 / 6
n
0
(1)
n n
i 1
19、
n
x i
x n
1
1 / x
1
x
1, n 0
(2)
i
0
n
2i 1
2n
1
n
1
(3)
i 1
n
2i
1
n 2
n
1
(4)
i 1
1.16 寫一算法，自大至小依次 出 序 入的三個(gè)整數(shù)
X， Y 和 Z 的
解：
int max3(int x,int y,int z)
{
if(x>y)
20、
if(x>z) return x;
else return z;
else
if(y>z) return y;
else return z;
}
1.17 已知 k 斐波那契序列的定
f 0
0 ，
f1
0 ， ?，
f k
2
0 ，
fk 1
1；
f n
f n 1
f n 2
fn k ， n
k ,k
1,
寫求
k 21、 斐波那契序列的第
m 的函數(shù)算法，
k 和 m均以 用的形式在函數(shù)參數(shù)表中出 。
解： k>0 數(shù)，
n 數(shù)列的第
n 項(xiàng)
int Fibonacci(int k,int n)
{
if(k<1) exit(OVERFLOW);
int *p,x;
p=new int[k+1];
if(!p) exit(OVERFLOW);
int i,j;
for(i=0;i 22、r(i=k+1;i 23、edef enum{Female,Male} SexType;
typedef struct{
char event[3]; // 目
SexType sex;
SchoolName school;
int score;
} Component;
typedef struct{
int MaleSum;
// 男 分
int FemaleSum;
/ /
女 分
int TotalSum; //
體 分
} Sum;
Sum SumScor 24、e(SchoolName sn,Component a[],int n)
{
Sum temp;
temp.MaleSum=0;
temp.FemaleSum=0;
temp.TotalSum=0;
int i;
for(i=0;i 25、p.MaleSum+temp.FemaleSum;
return temp;
}
1.19 寫算法， 算
i!* 2i
的 并存入數(shù)
a[0..arrsize-1]
的第
i-1
個(gè)分量中
(i=1,2,
?,n)
。假
算機(jī)中允 的整數(shù)最大
maxint
， 當(dāng)
n>arrsize
或 某個(gè)
k 1
k
26、
n
，使
k!?2
k
max int
，
按出 理。注意 你 好的出 理方法。
解：
#include 27、n>>k;
if(k>ArrSize-1) exit(0);
for(i=0;i<=k;i++){
if(i==0) a[i]=1;
else{
if(2*i*a[i-1]>MAXINT) exit(0);
else a[i]=2*i*a[i-1];
}
}
for(i=0;i<=k;i++){
if(a[i]>MAXINT) exit(0);
else cout< 28、值 Pn x0
，并確定算法中每一語(yǔ)句的執(zhí)行次數(shù)
i 0
和整個(gè)算法的時(shí)間復(fù)雜度。 注意選擇你認(rèn)為較好的輸入和輸出方法。
本題的輸入為 ai i
0,1, , n ，x0
和 n ，輸出為 Pn
x0 。
解：
#include 29、
double x;
int n,i;
int a[N];
cout<<"
輸入變量的值 x:";
cin>>x;
cout<<" 輸入多項(xiàng)式的階次 n:";
cin>>n;
if(n>N-1) exit(0);
cout<<" 輸入多項(xiàng)式的系數(shù) a[0]--a[n]:";
for(i=0;i<=n;i++) cin>>a[i];
cout<<"The polynomail value is "< 30、 31、結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為
了方便對(duì)鏈表的操作。它可以對(duì)空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。
2.2 填空題。
解： (1) 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與
元素
在表中的位置有關(guān)。
(2) 順序表中邏輯上相鄰的元素的物理位置
必定緊鄰。單鏈表中邏輯上相鄰的元素的物理位置
不一定
緊鄰。
(3) 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn) 32、的存儲(chǔ)位置由
其前驅(qū)結(jié)點(diǎn)的鏈域的值 指示。
(4) 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊處理 。
2.3 在什么情況下用順序表比鏈表好？
解：當(dāng)線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲(chǔ)的時(shí)候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行隨機(jī)存取。
2.4 對(duì)以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。
解：
33、
2.5 畫出執(zhí)行下列各行語(yǔ)句后各指針及鏈表的示意圖。
L=(LinkList)malloc(sizeof(LNode)); P=L;
for(i=1;i<=4;i++){
P->next=(LinkList)malloc(sizeof(LNode));
P=P->next; P->data=i*2-1;
}
P->next=NULL;
for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);
for(i=1;i<=3;i++) Del_LinkList(L,i);
解：
34、
2.6 已知 L 是無(wú)表頭結(jié)點(diǎn)的單鏈表，且 P 結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中
選擇合適的語(yǔ)句序列。
a. 在 P 結(jié)點(diǎn)后插入 S 結(jié)點(diǎn)的語(yǔ)句序列是 __________________。
b. 在 P 結(jié)點(diǎn)前插入 S 結(jié)點(diǎn)的語(yǔ)句序列是 __________________。
c. 在表首插入 S 結(jié)點(diǎn)的語(yǔ)句序列是 __________________。
d. 在表尾插入 S 結(jié)點(diǎn)的語(yǔ)句序列是 __________________。
(1) P->next=S;
(2) P->next=P-> 35、next->next;
(3) P->next=S->next;
(4) S->next=P->next;
(5) S->next=L;
(6) S->next=NULL;
(7) Q=P;
(8) while(P->next!=Q) P=P->next;
(9) while(P->next!=NULL) P=P->next;
(10) P=Q;
(11) P=L;
(12) L=S;
(13) L=P;
解： a. (4) (1)
b. (7) (11) (8) (4) (1)
c. (5) (12)
36、d. (9) (1) (6)
2.7 已知 L 是帶表頭結(jié)點(diǎn)的非空單鏈表，且 P 結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答
案中選擇合適的語(yǔ)句序列。
a. 刪除
b. 刪除
P 結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是 P 結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是
____________________ 。
____________________ 。
c. 刪除 P 結(jié)點(diǎn)的語(yǔ)句序列是 ____________________。
d. 刪除首元結(jié)點(diǎn)的語(yǔ)句序列是 ____________________。 e. 刪除尾元結(jié)點(diǎn)的 37、語(yǔ)句序列是 ____________________。
(1) P=P->next;
(2) P->next=P;
(3) P->next=P->next->next;
(4) P=P->next->next;
(5) while(P!=NULL) P=P->next;
(6) while(Q->next!=NULL) { P=Q; Q=Q->next; }
(7) while(P->next!=Q) P=P->next;
(8) while(P->next->next!=Q) P=P->next;
(9) while(P->next->n 38、ext!=NULL) P=P->next;
(10) Q=P;
(11) Q=P->next;
(12) P=L;
(13) L=L->next;
(14) free(Q);
解： a. (11) (3) (14)
b. (10) (12) (8) (3) (14)
c. (10) (12) (7) (3) (14)
d. (12) (11) (3) (14)
e. (9) (11) (3) (14)
2.8 已知 P 結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。
a. 在 P 結(jié)點(diǎn) 39、后插入 S 結(jié)點(diǎn)的語(yǔ)句序列是 _______________________。
b. 在 P 結(jié)點(diǎn)前插入 S 結(jié)點(diǎn)的語(yǔ)句序列是 _______________________。
c. 刪除 P 結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是 _______________________。
d. 刪除 P 結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是 _______________________。
e. 刪除 P 結(jié)點(diǎn)的語(yǔ)句序列是 _______________________。
(1) P->next=P->next->next;
(2) P->priou=P- 40、>priou->priou;
(3) P->next=S;
(4) P->priou=S;
(5) S->next=P;
(6) S->priou=P;
(7) S->next=P->next;
(8) S->priou=P->priou;
(9) P->priou->next=P->next;
(10) P->priou->next=P;
(11) P->next->priou=P;
(12) P->next->priou=S;
(13) P->priou->next=S;
(14) P->next->priou=P-> 41、priou;
(15) Q=P->next;
(16) Q=P->priou;
(17) free(P);
(18) free(Q);
解： a. (7) (3) (6) (12)
b. (8) (4) (5) (13)
c. (15) (1) (11) (18)
d. (16) (2) (10) (18)
e. (14) (9) (17)
2.9 簡(jiǎn)述以下算法的功能。
(1) Status A(LinkedList L) { //L 是無(wú)表頭結(jié)點(diǎn)的單鏈表
if(L && L->next) {
Q=L; L=L->n 42、ext; P=L;
while(P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return OK;
}
(2) void BB(LNode *s, LNode *q) {
p=s;
while(p->next!=q) p=p->next;
p->next =s;
}
void AA(LNode *pa, LNode *pb) {
//pa 和 pb 分別指向單循環(huán)鏈表中的兩個(gè)結(jié)點(diǎn)
BB(pa,pb);
BB(pb,pa);
}
解： ( 43、1) 如果 L 的長(zhǎng)度不小于 2，將 L 的首元結(jié)點(diǎn)變成尾元結(jié)點(diǎn)。
(2) 將單循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表。
2.10 指出以下算法中的錯(cuò)誤和低效之處，并將它改寫為一個(gè)既正確又高效的算法。
Status DeleteK(SqList &a,int i,int k)
{
// 本過(guò)程從順序存儲(chǔ)結(jié)構(gòu)的線性表a 中刪除第 i 個(gè)元素起的 k 個(gè)元素
if(i<1||k<0||i+k>a.length) return INFEASIBLE;//
參數(shù)不合法
else {
for(count=1;count 44、
// 刪除第一個(gè)元素
for(j=a.length;j>=i+1;j--) a.elem[j-i]=a.elem[j];
a.length--;
}
return OK;
}
解：
Status DeleteK(SqList &a,int i,int k)
{
// 從順序存儲(chǔ)結(jié)構(gòu)的線性表 a 中刪除第 i 個(gè)元素起的 k 個(gè)元素
// 注意 i 的編號(hào)從 0 開(kāi)始
int j;
if(i<0||i>a.length-1||k<0||k>a.length-i) return INFEASIBLE;
45、
for(j=0;j<=k;j++)
a.elem[j+i]=a.elem[j+i+k];
a.length=a.length-k;
return OK;
}
2.11 設(shè)順序表 va 中的數(shù)據(jù)元素遞增有序。試寫一算法，將 x 插入到順序表的適當(dāng)位置上，以保持該表的
有序性。
解：
Status InsertOrderList(SqList &va,ElemType x)
{
// 在非遞減的順序表 va 中插入元素 x 并使其仍成為順序表的算法
int i;
if(va.length==va.listsize)r 46、eturn(OVERFLOW);
for(i=va.length;i>0,x 47、表。若
A
B
空表，則
A
B ；若
A
=空表，而
B
空表，或者兩者均不為空表，且
A
的首元小于
B
的首元，則
A
B ；否則
A
B 。試寫一個(gè)比較
A ， B 大小的算法。
解：
Status CompareOrderList(SqList &A,SqList &B)
{
int i,k,j;
k=A.length>B.length?A.length: 48、B.length;
for(i=0;i 49、
int i=0;
LinkList p=L;
while(p&&p->data!=x){
p=p->next;
i++;
}
if(!p) return 0;
else return i;
}
2.14 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作 Length(L) 。
解：
// 返回單鏈表的長(zhǎng)度
int ListLength_L(LinkList &L)
{
int i=0;
LinkList p=L;
if(p) p=p-next;
while(p){
p 50、=p->next;
i++;
}
return i;
}
2.15 已知指針 ha 和 hb 分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長(zhǎng)度分別為 m和 n。試寫一算
法將這兩個(gè)鏈表連接在一起， 假設(shè)指針 hc 指向連接后的鏈表的頭結(jié)點(diǎn)， 并要求算法以盡可能短的時(shí)間完成
連接運(yùn)算。請(qǐng)分析你的算法的時(shí)間復(fù)雜度。
解：
void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc)
{
LinkList pa,pb;
pa=ha;
pb=hb;
while(p 51、a->next&&pb->next){
pa=pa->next;
pb=pb->next;
}
if(!pa->next){
hc=hb;
while(pb->next) pb=pb->next;
pb->next=ha->next;
}
else{
hc=ha;
while(pa->next) pa=pa->next;
pa->next=hb->next;
}
}
2.16 已知指針 la 和 lb 分別指向兩個(gè)無(wú)頭結(jié)點(diǎn)單鏈表中的首元結(jié)點(diǎn)。下列算法是從表 la 中刪除自第 i 個(gè)元素起共 len 個(gè)元素 52、后，將它們插入到表 lb 中第 i 個(gè)元素之前。 試問(wèn)此算法是否正確？若有錯(cuò)， 請(qǐng)改正之。 Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len) {
if(i<0||j<0||len<0) return INFEASIBLE;
p=la; k=1;
while(k 53、 }
s->next=p; q->next=s->next;
return OK;
}
解：
Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)
{
LinkList p,q,s,prev=NULL;
int k=1;
if(i<0||j<0||len<0) return INFEASIBLE;
// 在 la 表中查找第 i 個(gè)結(jié)點(diǎn)
p=la;
while(p&&k 54、>next;
k++;
}
if(!p)return INFEASIBLE;
// 在 la 表中查找第 i+len-1 個(gè)結(jié)點(diǎn)
q=p; k=1;
while(q&&k 55、ext=lb;
lb=p;
}
else{
s=lb; k=1;
while(s&&k 56、Delete(L,i) ，并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)
行比較。
2.19 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效的算法，刪除表中所有
值大于 mink 且小于 maxk的元素（若表中存在這樣的元素） ，同時(shí)釋放被刪結(jié)點(diǎn)空間， 并分析你的算法的時(shí)
間復(fù)雜度（注意， mink 和 maxk 是給定的兩個(gè)參變量，它們的值可以和表中的元素相同，也可以不同） 。
解：
Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk)
{
LinkLi 57、st p,q,prev=NULL;
if(mink>maxk)return ERROR;
p=L;
prev=p;
p=p->next;
while(p&&p->data 58、操作后的線性表中所有
元素的值均不相同） ，同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度。
解：
void ListDelete_LSameNode(LinkList &L)
{
LinkList p,q,prev;
p=L;
prev=p;
p=p->next;
while(p){
prev=p;
p=p->next;
if(p&&p->data==prev->data){
prev->next=p->next;
q=p;
p=p->next;
free(q);
}
59、
}
}
2.21 試寫一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線性表
a1 ,
, an
逆置為
an ,
, a1
。
解：
// 順序表的逆置
Status ListOppose_Sq(SqList &L)
{
int i;
ElemType x;
for(i=0;i 60、L.length-1-i]=x;
}
return OK;
}
2.22 試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。
解：
// 帶頭結(jié)點(diǎn)的單鏈表的逆置
Status ListOppose_L(LinkList &L)
{
LinkList p,q;
p=L;
p=p->next;
L->next=NULL;
while(p){
q=p;
p=p->next;
q->next=L->next;
L->next=q;
}
return OK;
}
2.23 設(shè)線性表
61、
A
a1 , a2 ,
, am
， B
b1 ,b2 ,
,bn
，試寫一個(gè)按下列規(guī)則合并
A，B 為線性表
C 的算法，即使得
C a1, b1 ,
, am , bm , bm 1 ,
,bn
當(dāng) m
n 時(shí)；
C a1, b1 ,
, an , bn
, an 1 ,
, am
當(dāng) m
n 時(shí)。
62、線性表 A，B 和 C 均以單鏈表作存儲(chǔ)結(jié)構(gòu)，且 C表利用 A 表和 B 表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L(zhǎng)度
值 m和 n 均未顯式存儲(chǔ)。解：
// 將合并后的結(jié)果放在 C 表中，并刪除 B 表
Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C)
{
LinkList pa,pb,qa,qb;
pa=A->next;
pb=B->next;
C=A;
while(pa&&pb){
qa=pa; qb=pb;
pa=pa->next; pb=pb->next;
63、
qb->next=qa->next;
qa->next=qb;
}
if(!pa)qb->next=pb;
pb=B;
free(pb);
return OK;
}
2.24 假設(shè)有兩個(gè)按元素值遞增有序排列的線性表 A 和 B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法將表歸并成一個(gè)按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表利用原表（即 A 表和 B 表）的結(jié)點(diǎn)空間構(gòu)造 C 表。
A 表和 B
C，并要求
解：
// 將合并逆置后的結(jié)果放在 C 表中，并刪除 B 表
S 64、tatus ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)
{
LinkList pa,pb,qa,qb;
pa=A;
pb=B;
qa=pa; // 保存
qb=pb; // 保存
pa 的前驅(qū)指針
pb 的前驅(qū)指針
pa=pa->next;
pb=pb->next;
A->next=NULL;
C=A;
while(pa&&pb){
if(pa->data 65、ext;
qa->next=A->next; // 將當(dāng)前最小結(jié)點(diǎn)插入 A 表表頭
A->next=qa;
}
else{
qb=pb;
pb=pb->next;
qb->next=A->next; // 將當(dāng)前最小結(jié)點(diǎn)插入 A 表表頭
A->next=qb;
}
}
while(pa){
qa=pa;
pa=pa->next;
qa->next=A->next;
A->next=qa;
}
while(pb){
qb=pb;
pb=pb->next;
qb- 66、>next=A->next;
A->next=qb;
}
pb=B;
free(pb);
return OK;
}
2.25 假設(shè)以兩個(gè)元素依值遞增有序排列的線性表
同），現(xiàn)要求另辟空間構(gòu)成一個(gè)線性表 C，其元素為
A 和 B 分別表示兩個(gè)集合（即同一表中的元素值各不相
A 和 B 中元素的交集，且表 C 中的元素有依值遞增有序
排列。試對(duì)順序表編寫求
C 的算法。
解：
// 將 A、 B 求交后的結(jié)果放在 C 表中
Status ListCross_Sq(SqList &A,SqList &B,SqList &C)
{
int i=0,j=0,k=0;
while(i
- 溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年高考政治一輪復(fù)習(xí)：統(tǒng)編版選擇性必修1-3【共3冊(cè)重點(diǎn)知識(shí)點(diǎn)匯總】
- 2025年高考政治一輪復(fù)習(xí)：七冊(cè)教材重點(diǎn)考點(diǎn)匯總
- 2025年高考生物一輪復(fù)習(xí)：高中生物必修+選必修5冊(cè)教材重點(diǎn)知識(shí)點(diǎn)匯總
- 2025政府工作報(bào)告要點(diǎn)速覽發(fā)展總體要求和政策取向
- 《哪吒2》與DEEPSEEK年輕力量的崛起助力中國(guó)突破重圍
- 建設(shè)金融強(qiáng)國(guó)做好金融五篇大文章的指導(dǎo)意見(jiàn)
- 落實(shí)高質(zhì)量發(fā)展要求如期完成既定目標(biāo)任務(wù)更新理念科學(xué)統(tǒng)籌切實(shí)增強(qiáng)規(guī)劃執(zhí)行的系統(tǒng)性整體性協(xié)同性
- 如何成為一名暖護(hù)暖護(hù)的概念與職責(zé)
- 藥品儲(chǔ)存與養(yǎng)護(hù)醫(yī)療護(hù)理藥品儲(chǔ)存藥品養(yǎng)護(hù)藥品常識(shí)
- 手術(shù)室職業(yè)暴露與防護(hù)診療護(hù)理等過(guò)程中被患者血液體液等污染自身皮膚或黏膜導(dǎo)致的感染
- XX企業(yè)中層管理者領(lǐng)導(dǎo)力提升培訓(xùn)課程
- 醫(yī)院新員工入職培訓(xùn)醫(yī)院新員工必備主要職業(yè)意識(shí)醫(yī)院新員工必備工作觀
- 人工智能技術(shù)介紹人工智能DeepSeek人工智能的未來(lái)展望與發(fā)展
- 養(yǎng)娃要有松弛感家庭教育讓孩子在具有松弛感的家庭里慢慢成長(zhǎng)
- 醫(yī)院新員工入職培訓(xùn)醫(yī)院新員工必備主要職業(yè)意識(shí)
相關(guān)資源
更多