有需要河北科技大學計算機專碩考研真題的同學，私信留下郵箱即可。

第一章、緒論作業

一、填空題

1.算法的時間復雜度除了與問題的規模有關外，還與待處理的數據的（待處理數據的初態 ）有關。

2.把長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法，其時間復雜度為（ O（m） ）。

3.假設時間復雜度為O（nlogn）的算法在有256個元素的數組上運行需要4ms，則在具有512個元??? 素的數組上運行需要（ 9 ）ms。

解析：此題可按照比例計算，將256和512分別代入時間復雜度計算公式然后分別比上自己需要的時間，即可求出具有512個元素的數組運行所需要的時間。這里的logn是以2為底的對數，還有一種解法：設一個系數k，根據k*256log256=4，即可求出k的值，然后再代入計算k*512log512即可得出運行時間。

二、分析算法時間復雜度

設n是偶數，下面程序段中語句y=y+i*j的執行次數是多少？該算法的時間復雜度是多少？要求列出計算公式。?

for (i=1;i<=n;i++)if(2*i<=n)for (j=2*i; j<=n; j++)y=y+i*j;

解析：總執行次數為：(n-1)+(n-3)+...+3+1=n2/4；算法時間復雜度O(n^2)。這個題做的時候就是列出語句的執行次數，然后自己去找規律。

第二章、線性表作業

一、選擇題 1.對順序存儲的線性表，設其長度為 20，在任何位置上插入或刪除操作都是等概率的。插入 一個元素時平均要移動表中的（A）個元素。 A.10 ? ? ? ? ???????????????????? B.9? ? ? ? ? ? ? ? ? ? ? ? ? ?? C.11 ? ? ? ? ? ?? ? ? ?? D．12 2、若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采 用（D）存儲方式最節省運算時間。 A.單鏈表???? ?? B.僅有頭指針的單循環鏈表 ? ??? C.雙鏈表 ? ? ? D.僅有尾指針的單循環鏈表?
? 3、對線性表采用折半查找法，該線性表必須（B）。 A．采用順序存儲結構 ? ? ? ? ? ? ??????????????????? B．采用順序存儲結構，且元素按值有序 C．采用鏈式存儲結構 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? D．采用鏈式存儲結構，且元素按值有序 4．線性表采用鏈式存儲時，其地址(D) 。 A. 必須是連續的?? B. 部分地址必須是連續的?? C. 一定是不連續的??? D. 連續與否均可以 5．對順序存儲的線性表，設其長度為 n，在任何位置上插入或刪除操作都是等概率的。插入 一個元素時平均要移動表中的（A）個元素。 A. n/2????????????????? B.(n+1)/2?????????????????? C.(n-1)/2 ? ? ? ? ? ? ? ? ? ?? D. n 6．在有 15 個元素的順序表中，刪除一個元素時，平均移動元素的次數為(B)。 A．14 ? ? ? ? ? ? ? ?? B．7???????????????????????? C．15 ? ? ? ? ? ? ? ? ? ? ? ?? D．8

二、填空題

1、帶頭結點的循環鏈表L為空的條件是???L->next==L ?????????????。

2.存取結構是在一個數據結構上對查詢操作的時間性能的一種描述，通常有兩種存取結構：順序存取和?隨機存取 ?。（還有索引存取和散列存取，共4種存取結構。）

3.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法，其時間復雜度度為??O(m) ?。

4.在循環雙鏈表中，完成新結點S插入到結點P后面的操作，需要修改四個指針：?s->prior=p?；?s->next=p->next ??；?p->next->prior=s ??； ???p->next=s ???；

5. 在循環雙鏈表中，設指針p 指向待刪除結點，刪除操作需要兩條語句：?p->prior->next=p->next ；??p->next->prior=p->prior ??。

6.設有一個雙鏈表，每個結點中除了有Prior、Data和Next三個分量外，還有訪問頻度分量Fred，根據題意寫出該結點的存儲結構定義，結點名稱為DulNode。
?

Typedef struct DulNode { Elemtype data;Int freq;Struct DulNode *prior,*next; }DulNode;

三、判斷題

（ 錯 ）1、線性表的邏輯順序與存儲順序總是一致的。

（ 錯）2、在單鏈表中要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構。

（ 錯）3、線性表的鏈式存儲結構優于順序存儲結構。

（ 錯）4、算法的原地工作的含義是指不需要任何額外的輔助空間。

四、算法設計題

1. 已知帶頭結點的單鏈表L，試寫一算法將單鏈表逆置。（12分）

//原地將鏈表逆置 typedef struct LNode {ElemType data;struct LNode *next ; }LNode, *LinkList; 2分void Inverse( LinkList L) 1分 {p = L->next; 2 分 L->next = NULL; 1 分 while (p != NULL) 2 分 {q = p->next; 1 分 p->next = L-next; 1 分 L->next = p; 1分 p = q; 1 分 } }//創建新鏈表逆置 LinkList* new,p; new=NULL; if(L==NULL) return 0; p=L->next; L->next=NULL; while(p) {p->next=new;new=p;p=p->next; } L->next=new;

2.設有不帶頭結點單鏈表L，結點結構為? ，以數據域的值非遞減有序排列，現插入一個數據為e的元素，使得插入后仍然有序，編寫此算法。（12分）
?

void InsertOrder(LinkList L, DataType e) 1分 {ListNode *s, *p, *pre;s = (ListNode *)malloc(sizeof(ListNode)); //或s=new ListNode; 1分s->data = e; 1分 if(L==NULL||e<p->data) 1分{s->next=L; L=s; return; 1分} pre = L; p = L->next; 1分 while(p!=NULL && p->data<=e) 2分 {pre = p; p = p->next; 2分 } pre->next = s; 1分 s->next = p; 1分 }

3.帶頭結點的單鏈表Ｌ，判斷非空單鏈表是否遞增有序。（12分）

Int increase(Node *first) 2分 {P=first->next; 2分 While(p->next!=NULL) 2分{q=p->next; 2分if (p->data<q->data) p=q; 2分Else return 0; 1分 }Return 1; 1分 }

４.已經帶頭結點的單鏈表，頭指針為first，復制該單鏈表。（12分）

Node *Copy(Node *first) 2分 {Head=(Node*)malloc(sizeof(Node));//headwz 新鏈表的頭指針 1分P=first->next;r=head; //工作指針p和尾指針r分別初始化 1分While(P!=NULL) 2分{ S=(Node*) malloc(sizeof(Node));s->data=p->data; //復制結點 2分r->next=s;r=s; //尾插法插入新鏈表1分p=p->next; 1分}r->next=NULL; 1分 return head; 1分 }

5.?假設在長度大于1的循環單鏈表中，既無頭結點也無頭指針，S為指向單鏈表中某個結點的指針，試編寫算法刪除結點S的前驅結點；寫出該結點的存儲結構定義。（12分）

void Del(Node *s) 2分 {p=s; 2分while(p->next->next != s) 2分p=p->next; 1分r=p->next; 1分p->next=s; 2分free(r); 2分 }

總結

以上是生活随笔為你收集整理的河北科技大学——数据结构课后习题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。