作業6-改進的單連結清單及其應用

2-1

對于一非空的循環單連結清單，

h和p分别指向連結清單的頭、尾結點，則有：(A)

A.p->next == h

B.p->next == null

C.p == null

D.p == h

2-2

在雙向循環連結清單結點p之後插入s的語句是：(D)

A.p->next=s; s->prior=p; p->next->prior=s ; s->next=p->next;

B.p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;

C.s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;

D.s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;

2-3

在雙向連結清單存儲結構中，删除p所指的結點，相應語句為：©

A.p->prior=p->prior->prior; p->prior->next=p;

B.p->next->prior=p; p->next=p->next->next;

C.p->prior->next=p->next; p->next->prior=p->prior;

D.p->next=p->prior->prior; p->prior=p->next->next;

2-4

某線性表中最常用的操作是在最後一個元素之後

插入一個元素和删除第一個元素，

則采用什麼存儲方式最節省運算時間？(B)

A.單連結清單

B.僅有尾指針的單循環連結清單

C.僅有頭指針的單循環連結清單

D.雙連結清單

[解析]對C,若要在最後插入一個元素,那麼隻有頭指針你還得周遊到最後

對D,雙連結清單但不是循環的,那麼在最後位置插入和頭指針的情況一樣

2-5

若某表最常用的操作是在最後一個結點之後

插入一個結點或删除最後一個結點。

則采用哪種存儲方式最節省運算時間？()

A.單連結清單

B.雙連結清單

C.單循環連結清單

D.帶頭結點的雙循環連結清單

[解析]ABC在最後插入節點都需要周遊一遍連結清單

2-6

将線性表La和Lb頭尾連接配接，要求時間複雜度為O(1)，

且占用輔助空間盡量小。應該使用哪種結構？(D)

A.單連結清單

B.單循環連結清單

C.帶尾指針的單循環連結清單

D.帶頭結點的雙循環連結清單

[解析]AB需要周遊連結清單,C隻需要修改兩個尾指針的内容

并且釋放掉第二個連結清單的頭指針即可

D時間是O(1),但是空間使用率不如C

2-7

(neuDS)在連結清單中若經常要删除表中最後一個結點或在

最後一個結點之後插入一個新結點，則宜采用()存儲方式。©

A.順序表

B.用頭指針辨別的循環單連結清單

C.用尾指針辨別的循環單連結清單

D.雙向連結清單

[解析]我感覺C也好像不太好,在删除最後一個節點的時候

還是需要周遊連結清單

2-8

非空的循環單連結清單head的尾結點（由p所指向）滿足()。©

A.p->next == NULL

B.p == NULL

C.p->next == head

D.p == head

2-9

在循環雙連結清單的p所指結點之前插入s所指結點的操作是()。(D)

A.p->prior = s; s->next = p; p->prior->next = s; s->prior = p->prior;

B.p->prior = s; p->prior->next = s; s->next = p; s->prior = p->prior;

C.s->next = p; s->prior = p->prior; p->prior = s; p->right->next = s;

D.s->next = p; s->prior = p->prior; p->prior->next = s; p->prior = s;

2-10

若某表最常用的操作是在最後一個結點之後插入一個結點或删除最後一個結點，

則采用()存儲方式最節省運算時間。(D)

A.單連結清單

B.給出表頭指針的單循環連結清單

C.雙連結清單

D.帶表頭附加結點的雙循環連結清單

2-11

某線性表最常用的操作是在最後一個結點之後

插入一個結點或删除第一個結點，故采用()存儲方式最節省運算時間。(D)

A.單連結清單

B.僅有頭結點的單循環連結清單

C.雙連結清單

D.僅有尾指針的單循環連結清單

2-12

在一個長度為n（n>1)的單連結清單上，設有頭和尾兩個指針，

執行()操作與連結清單的長度有關。(B)

A.删除單連結清單中的第一個元素

B.删除單連結清單中的最後一個元素

C.在單連結清單第一個元素前插入一個新元素

D.在單連結清單最後一個元素後插入一個新元素

[解析]删除最後一個元素需要知道前一個元素的位址

2-13

如果對線性表的運算隻有4種，即删除第一個元素，删除最後一個元素，

在第一個元素前面插入新元素，

在最後一個元素的後面插入新元素，則最好使用()。©

A.隻有表尾指針沒有表頭指針的循環單連結清單

B.隻有表尾指針沒有表頭指針的非循環雙連結清單

C.隻有表頭指針沒有表尾指針的循環雙連結清單

D.既有表頭指針也有表尾指針的循環單連結清單

[解析]主要還是删除最後一個節點遇到的問題,需要知道前一個節點的位址

2-14

如果對線性表的運算隻有2種，即删除第一個元素，

在最後一個元素的後面插入新元素，則最好使用()。(B)

A.隻有表頭指針沒有表尾指針的循環單連結清單

B.隻有表尾指針沒有表頭指針的循環單連結清單

C.非循環雙連結清單

D.循環雙連結清單

2-15

在雙向循環連結清單中，在p所指的結點之後插入s指針所指的結點，其操作是()。(D)

A.p->next = s; s->prior = p; (p->next)->prior = s; s->next = p->next;

B.s->prior = p; s->next = p->next; p->next = s; p->next->prior = s;

C.p->next = s; p->next->prior = s; s->prior = p; s->next = p->next;

D.s->prior = p; s->next = p->next; p->next->prior = s; p->next = s;

2-16

帶表頭附加結點的雙向循環連結清單為空的判斷條件是頭指針L滿足條件()。(D)

A.L= =NULL

B.L->right= =NULL

C.L->left = =NULL

D.L->right= =L

2-17

循環連結清單的主要優點是()。(D)

A.不再需要頭指針了

B.已知某個結點的位置後，能夠很容易找到它的直接前驅

C.在進行插入、删除運算時，能更好的保證連結清單不斷開

D.從表中的任意結點出發都能掃描到整個連結清單

[解析]優點在周遊的時候展現

2-18

已知指針ha和hb分别是兩個單連結清單的頭指針，

下列算法将這兩個連結清單首尾相連在一起，并形成一個循環連結清單

（即ha的最後一個結點連結hb的第一個結點，

hb的最後一個結點指向ha），

傳回該循環連結清單的頭指針。請将該算法補充完整。(B)

typedef struct node{

ElemType data;

struct node *next;

}LNode;

LNode *merge(LNode *ha, LNode *hb) {

LNode *p=ha;

if (haNULL || hbNULL) {

cout<<”one or two link lists are empty!”<<endl;

return NULL;

}

while ( p->next!=NULL )

p=p->next;

p->next=hb;

while ( p->next!=NULL )

p=p->next;

__________

}

A.ha=p->next; return ha;

B.p->next=ha; return ha;

C.ha=p->next; return p;

D.p->next=ha; return p;

[解析]這倆連結清單應該是沒有頭結點

2-19

設有一個雙向循環連結清單，每個結點中除有left、data和right三個域外，

還增設了一個通路頻度域freq，freq 的初值為零。每當連結清單進行一次查找操作後，

被通路結點的頻度域值便增1，同時調整連結清單中結點的次序，

使連結清單按結點頻度值非遞增有序的次序排列。下列算法是符合上述要求的查找算法，

請将該算法補充完整。©

typedef struct Node{

ElemType data;

struct Node *left;

struct Node *right;

intfreq;

} DNode;

DNode *locate_DList(DNode *&L, ElemType x)

{ //在表L中查找元素x，查找成功則調整結點頻度域值及結點位置，并傳回結點位址；

//查找不成功則傳回NULL

DNode *p=L, *q;

if (LNULL) return NULL;

while (p->data!=x && p->right!=L) p=p->right;

if (p->data!=x) return NULL;

p->freq++;

q=p->left;

while (q!=L && q->freq<=p->freq) q=q->left; //查找插入位置

if (qL && q->freq<=p->freq) { //需将p結點插在頭結點L前

//将p結點先從連結清單中摘下來

p->left->right=p->right;

p->right->left=p->left;

//将p結點插在L結點前

p->right=L;

p->left=L->left;

L->left->right=p;

L->left=p;

L=p;

}

else if (q!=p->left ) { //若q不是p的前驅，則需調整結點位置，将p結點插在q結點後

//将p結點先從連結清單中摘下來

p->left->right=p->right;

p->right->left=p->left;

______________ //将p結點插在q結點後

}

return p;

}

A.p->left=q; p->right=q->right;

B.p->left=q; q->right=p;

C.p->left=q; p->right=q->right; q->right->left=p; q->right=p;

D.p->left=q; q->right=p; p->right=q->right; q->right->left=p;

2-20

與單連結清單相比，雙連結清單的優點之一是()。(D)

A.插入、删除操作更加簡單

B.可随機通路

C.可以省略表頭指針或表尾指針

D.順序通路相鄰結點更加靈活

[解析]不太了解順序是啥意思,但是通路一個節點的相鄰節點确實更友善了

2-21

采用多項式的非零項鍊式存儲表示法，如果兩個多項式的非零項分别為N1和N2個，

最高項指數分别為M1和M2，則實作兩個多項式相乘的時間複雜度是：(A)

A.O(N1×N2)

B.O(M1×M2)

C.O(N1+N2)

D.O(M1+M2)

6-1 帶頭結點的單連結清單就地逆置 (9分)
/* 請在這裡填寫答案 */
//這是把元素提出來,一個一個重新逆序插傳入連結表L中
//不過要注意插入之前L->next要賦NULL,否則連結清單尾結點的next不為空
//輸出會死循環好像
void ListReverse_L(LinkList &L)
{
	LNode *temp = NULL;
	LNode *p = L->next;
    L->next = NULL;
	while (p)
	{
		temp = p;
		p = p->next;
		temp->next = L->next;
		L->next = temp;
	}
	return ;
}

前一個題越寫越亂,就放棄了

7-24 求鍊式線性表的倒數第K項 (20分)

#include <iostream>
#include <malloc.h>
using namespace std;
#define OVERFLOW -2

typedef int ElemType;
typedef struct DuLNode
{
	struct DuLNode* left, *right;
	ElemType data;
}DuLNode, *DuList;

void initList_DuL(DuList &L)
{
	L = (DuLNode*)malloc(sizeof(DuLNode));
	if (L == NULL) exit(OVERFLOW);
	L->left = L;
	L->right = L;
}
void AddNode(DuList &L)
{
	DuLNode *p = L;
	int num;
	while (cin >> num)
	{
		if (num < 0) break;
		DuLNode *temp_node = (DuLNode*)malloc(sizeof(DuLNode));
		if (temp_node == NULL) exit(OVERFLOW);
		temp_node->data = num;
		
		temp_node->left = p;
		temp_node->right = p->right;
		p->right = temp_node;
		L->left = temp_node;
		p = temp_node;
	}
}
int get_elem_in_k(DuList L, int k)
{
	DuLNode *p = L;
	for (int i = 0; i < k; i++)
	{
		if (p == L) return -1;
		p = p->left;
	}
	return p->data;
}
int main()
{
	int k;
	DuList L;
	initList_DuL(L);
	cin >> k;
	AddNode(L);
	int num = get_elem_in_k(L, k);
	if (num == -1) cout << "NULL" << endl;
	else cout << num;
	system("pause");
	return 0;
}

作業6-改進的單連結清單及其應用

繼續閱讀

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

百大球星評選｜詹眉領銜晉級巴特勒布克無緣前十今票選11-20

鍵盤俠丨陣容深厚的煩惱！湖人首發如何選？球迷：4号位濃眉可怕