計算機軟件技術基礎復習題及答案完美打印版

1、計算機軟件技術基礎試題1.線性表的鏈式存儲結構與順序存儲結構相比優(yōu)點是 。A. 所有的操作算法實現(xiàn)簡單B. 便于隨機存取C. 便于插入和刪除D. 便于利用零散的存儲器空間2.線性表是具有n個 的有限序列。A. 表元素B. 字符C. 數(shù)據(jù)元素D. 數(shù)據(jù)項E. 信息項3.若長度為n的線性表采用順序存儲結構，在其第I個位置插入一個新元素的算法的時間復雜度為 。（1In+1）A. O(0)B. O(1)C. O(n)D. O(n2)4.設A是一個線性表(a1,a2,an)，采用順序存儲結構，則在等概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為 ，平均每刪除一個元素需要移動的元素個數(shù)為 ；若元素插

2、在ai與ai+1之間(0In-1)的概率為，則平均每插入一個元素所要移動的元素個數(shù)為 ；A. B. C. D. 5.下列函數(shù)中，按它們在時的無窮大階數(shù)，最大的是 。A. lognB. nlognC. 2n/2D. n!spnextnextnext6.將下圖所示的s所指結點加到p所指的結點之后，其語句應為： 。A. s->next=p+1; p->next=s;B. (*p).next=s; (*s).next=(*p).next;C. s->next=p->next; p->next=s->next;D. s->next=p->next; p-&

3、gt;next=s;7.將兩個各有n個元素的有序表歸并為一個有序表時，其最少的比較次數(shù)是 。A. nB. 2n-1C. n-1D. 2n8.下面的程序段是合并兩個無頭結點鏈表(ha和 hb)為一個無頭結點鏈表ha的過程，作為參數(shù)的兩個鏈表都是按結點的data域由大到小鏈接的。合并后新鏈表的結點仍按此方式鏈接。請?zhí)顚懴率隹湛?，使程序能正確運行。#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;void combine(linklisttype *ha, linklisttype *hb)l

4、inklisttype *h, *p;h = (linklisttype *)malloc(sizeof(linklisttype);h->next = NULL;p = h;while(ha != NULL && hb != NULL)if(ha->data>=hb->data)/*較大的元素先插入*/p->next = (1) ;p = (2) ; (3) ;elsep->next = (4) ;p = (5) ; (6) ;if(ha=NULL) (7) ;if(hb=NULL) (8) ;ha = h->next;free(h)

5、;參考答案：CD C C BAC D D A (1) ha(2) p->next(3) ha=ha->next(4) hb(5) p->next(6) hb=hb->next(7) p->next=hb(8) p->next=ha9.如果表A中所有元素(a1,a2,an)與表B的一個順序子表(bk,bk+1,bk+n-1)完全相同（即a1=bk,a2=bk+1,an=bk+n-1），則稱表A包含在表B中。設ha，hb為帶頭結點的單鏈表，分別表示有序表A和B，下面的函數(shù)用于判別表A是否包含在表B中，若是，則返回true，否則返回false。（提示：用遞歸實現(xiàn)）

6、#define true 1#define false 0#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;int inclusion(linklisttype *ha, linklisttype *hb)linklisttype *pa, *pb;pa = ha->next;pb = hb->next; (1) ;while( (2) )if(pa->data=pb->data) (3) ;else (4) ; (5) ;參考答案：(1) if(pa=NULL)

7、 return(true)(2) pb!=NULL && pa->data>=pb->data(3) return(inclusion(pa, pb)(4) pb = pb->next;(5) return(false)10.在本題的程序中，函數(shù)create_link_list(n)建立一個具有n個結點的循環(huán)鏈表；函數(shù)josephus(n,I,m)對由create_link_list(n)所建立的具有n個結點的循環(huán)鏈表按一定的次序逐個輸出，并刪除鏈表中的所有結點。參數(shù)n(n>0)指明循環(huán)鏈表的結點個數(shù)，參數(shù)I(1In)指明起始結點，參數(shù)m（m>

8、;0是步長），指明從起始結點或前次被刪除并輸出的結點之后的第m個結點作為本次被輸出并刪除的結點。例如，對于下圖所示的具有6個結點的循環(huán)鏈表，在調用josephus(6,3,2)后，將輸出5,1,3,6,4,2。請在空框處填上適當內容，每框只填一個語句。#define NULL 0typedef struct nodeint data;struct node *next;node, linklisttype;linklisttype *create_link_list(int n)linklisttype *head, *p, *q;int I;head = NULL;if(n>0)hea

9、d = (linklisttype *)malloc(sizeof(linklisttype);p = head;for(I=1;I<=n-1;I+)/*此循環(huán)用于建立一個鏈表，鏈表的內容從1至n-1*/p->data = I;q = (linklisttype *)malloc(sizeof(linklistttype); (1) ; (2) ;p->data = n; (3) ;/*建立從尾鏈到首的環(huán)形結構*/return(head);void Josephus(int n, int j, int m)linklisttype *p, *q;int j;p = creat

10、e_link_list(n);for(;I>1;I-)p = p->next; (4) ;while(j<n)for(I=1;I<=m-1;I+)p = p->next; (5) ;printf(“%8d”,q->data); (6) ;free(q);j=j+1;參考答案：(1) p->next = q;(2) p = q;(3) p->next = head(4) j=0(5) q=p->next;(6) p->next = q->next11.在下列程序中，函數(shù)difference(A,B)用于求兩集合之差C=A-B，即當

11、且僅當e是A中的一個元素，且不是B中的元素時，e是C中的一個元素。集合用有序鏈表實現(xiàn)，用一個空鏈表表示一個空集合，表示非空集合的鏈表根據(jù)元素之值按遞增排列，執(zhí)行C=A-B之后，表示集合A和B的鏈表不變，若結果集合C非空，則表示它的鏈表應根據(jù)元素之值按遞增序排列。函數(shù)append()用于在鏈表中添加結點。#include <stdio.h>#define NULL 0typedef struct nodeint data;struct node *next;NODE;NODE *append(NODE *last, int x)last->next=(NODE *)malloc

12、(sizeof(NODE);last->next->data=x;return(last->next);NODE *difference(NODE *A ,NODE *B)NODE *C,*last;C=last=(NODE *)malloc(sizeof(NODE);while( (1) )if(A->data < B->data)last=append(last,A->data);A=A->next;elseif( (2) )A=A->next;B=B->next;else (3) ;while( (4) )last=append

13、(last,A->data);A=A->next; (5) ;last=C;C=C->next;free(last);return(C);參考答案：(1) A!=NULL & B!=NULL(2) A->data=B->data(3) B=B->next;(4) A!=NULL(5) last->next=NULL;12.閱讀以下算法，填充空格，使其成為完整的算法。其功能是在一個非遞減的順序存儲線性表中(從下標1處開始存儲)，刪除所有值相等的多余元素。#define MAXSIZE 30typedef structint elemMAXSIZE

14、;int length;/*表長*/sqlisttype;void exam21(sqlisttype *L)int i,j;i=1,j=2;while( (1) )if(L->elemi!=L->elemj)if(j!=(i+1) (2) ;L->length=L->length-(j-i-1); (3) ;else (4) ;if(j>L->length) (5) ;參考答案：(1) j<=L->length(2) for(int k=j;k<=L->length;k+)L->elemk-(j-i-1)=L->elem

15、k;(3) i+,j=i+1;(4)j+;(5)L->length=L->length-(j-i-1);break;13.用單鏈表表示的鏈式隊列的隊頭在鏈表的 A 位置。A. 鏈頭B. 鏈尾C. 鏈中14.若用單鏈表表示隊列，則應該選用 B 。A. 帶尾指針的非循環(huán)鏈表B. 帶尾指針的循環(huán)鏈表C. 帶頭指針的非循環(huán)鏈表D. 帶頭指針的循環(huán)鏈表15.在解決計算機主機與打印機之間速度不匹配問題時，通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則從該緩沖區(qū)中取出數(shù)據(jù)打印，先放入打印緩沖區(qū)的數(shù)據(jù)先被打印。該緩沖區(qū)應該是一個 B 結構。A. 堆棧B. 隊列C. 數(shù)組

16、D. 線性表16.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為 B 。A. 1和5B. 2和4C. 4和2D. 5和117.設棧的輸入序列為1,2，,10，輸出序列為a1,a2,a10，若a5=10，則a7為 C 。A. 4B. 8C.不確定D.718.設棧的輸入序列是1,2,3,4，則 D 不可能是其出棧序列。A 1243B. 2134C. 1432D. 431219.以下 D 是C語言中”abcd321ABCD”的子串。A. abcdB. 321ABC. “abcABC”D. “2

17、1AB”20.若串S=”software”，其子串的數(shù)目是 C 。A. 8B. 37C. 36D. 921.將一個A1:100,1:100的三對角矩陣，按行優(yōu)先存入一維數(shù)組B1:298中，A中元素A66,65(即該元素的下標)在B數(shù)組中位置k為 B 。A. 198B. 195C. 197D. 19622.設高為h的二叉樹只有度為0和2的結點，則此類二叉樹的結點數(shù)至少為 B ，至多為 F 。高為h的完全二叉樹的結點數(shù)至少為 E ，至多為 F 。A 2hB. 2h-1C. 2h+1D.h+1E. 2h-1F. 2h-1G. 2h+1-1H. 2h+123.一棵有124個葉結點的完全二叉樹，最多有

18、B 個結點。A. 247B. 248C. 249D. 25124.若從二叉樹的任一結點出發(fā)到根的路徑上所經過的結點序列按其關鍵字有序，則該二叉樹是 C 。A. 滿二叉樹B. 哈夫曼樹C. 堆D. 二叉查找樹25.前序遍歷和中序遍歷結果相同的二叉樹為 F ；前序遍歷和后序遍歷結果相同的二叉樹為 B 。A. 一般二叉樹B. 只有根結點的二叉樹C. 根結點無左孩子的二叉樹D. 根結點無右孩子的二叉樹E. 所有結點只有左孩子的二叉樹F. 所有結點只有右孩子的二叉樹26.具有n個結點的完全二叉樹，已經順序存儲在一維數(shù)組A1.n中，下面的算法是將A中順序存儲變?yōu)槎骀湵泶鎯Φ耐耆鏄?。請?zhí)顚戇m當語句在下

19、面的空格內，完成上述算法。#define MAXSIZE 30typedef struct btnodeint data;struct btnode *lchild, *rchild;BTN;void createtree(BTN *p,int A, int I,int n) (1) ;p->data=AI;if( (2) ) (3) ;elsep->lchild=NULL;if( (4) )createtree( (5) );elsep->rchild=NULL;void btree(BTN * p ,int A,int n)createtree(p,A,1,n);參考答案

20、：(1) p=(BTN *)malloc(sizeof(BTN)(2) 2*I<=n(3) createtree(p->lchild,A,2*I,n)(4) 2*I+1<=n(5) p->rchild,A,2*I+1,n27.若在線性表中采用折半查找法查找元素，該線性表應該 C 。A. 元素按值有序B. 采用順序存儲結構C. 元素按值有序，且采用順序存儲結構D. 元素按值有序，且采用鏈式存儲結構28.在分塊檢索中，對256個元素的線性表分成 16 塊最好，每塊的最佳長度是 16 ；若每塊的長度為8，其平均檢索長度為 21 。29.假定有K個關鍵字互為同義詞，若用線性探測

21、法把這K個關鍵字存入散列表中，至少要進行 D 次探測。A. K-1次B. K次C. K+1次D. K(K+1)/2次30.在n個記錄的有序順序表中進行折半查找，最大的比較次數(shù)是。31.Hash技術廣泛應用于查找過程，選擇Hash函數(shù)的標準是 和 。處理沖突的技術有優(yōu)有劣，其共同標準是 。32.在下述排序算法中，所需輔助存儲空間最多的是 B ，所需輔助存儲空間最小的是 C ，平均速度最快的是 A 。A.快速排序B. 歸并排序C. 堆排序33.在文件局部有序或文件長度較小的情況下，最佳內部排序的方法是 A 。A. 直接插入排序B. 冒泡排序C. 簡單選擇排序34.快速排序在最壞情況下時間復雜度是O

22、(n2)，比 A 的性能差。A. 堆排序B. 冒泡排序C. 簡單選擇排序35.若需在O(nlogn)的時間內完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是 C 。A. 快速排序B. 堆排序C. 歸并排序D. 希爾排序36.如果只想得到1000個元素組成的序列中第5個最小元素之前的部分排序的序列，用 B 方法最快。A. 冒泡排序B. 快速排序C. 希爾排序D. 堆排序E. 簡單選擇排序37.以下結點序列是堆的為 A 。A. 100,90,80,60,85,75,20,25,10,70,65,50B. 100,70,50,20,90,75,60,25,10,85,65,8038.若要盡

23、可能快地完成對實數(shù)數(shù)組的排序，且要求排序是穩(wěn)定的，則應選 C 。A. 快速排序B. 堆排序C. 歸并排序D. 希爾排序39.從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為 A 排序法。A. 插入排序B. 交換排序C. 選擇排序D. 歸并排序40.直接插入排序在最好情況下的時間復雜度為 B 。A. O(logn)B. O(n)C. O(nlogn)D. O(n2)41.下面函數(shù)是將任意序列調整為最大堆的算法，請將空白部分填上：將任意序列調整為最大堆通過不斷調用adjust函數(shù)，即for(i=n/2;i>0;i-) adjus

24、t(list, i, n);其中l(wèi)ist為待調整序列所在數(shù)組（從下標1開始），n為序列元素的個數(shù)。void adjust(int list, int root, int n)/*將以root為下標的對應元素作為待調整堆的根，待調整元素放在list數(shù)組中，最大元素下標為n*/int child,rootkey;rootkey = (1) ;child = 2*root;while(child < n)if(child<n) && (listchild<listchild+1) (2) ;if(rootkey > listchild)break;elseli

25、st (3) =listchild; (4) ;list (5) =rootkey;參考答案：(1) listroot(2) child+;(3) child/2(4) child *= 2;(5) child/241.表是一種數(shù)據(jù)結構，鏈表是一種 (1) 。隊列和棧都是線性表，棧的操作特性是 (2) ，隊列的操作特性是 (3) 。今有一空棧S，對下列待進棧的數(shù)據(jù)元素序列a,b,c,d,e,f依次進棧、進棧、出棧、進棧、進棧、出棧的操作，則此操作完成后，棧S的棧頂元素為 (4) ，棧底元素為 (5) 。供選答案：(1):A. 非順序存儲線性表B. 非順序存儲非線性表C. 順序存儲線性表D. 順

26、序存儲非線性表(2):A. 隨機進出B. 先進后出C. 先進先出D. 出優(yōu)于進(3):A. 隨機進出B. 先進后出C. 后進后出D. 進優(yōu)于出(4):A. fB. cC. aD. b(5):A. bB. cC. aD. d答案：ABCBC42.操作系統(tǒng)主要是對計算機系統(tǒng)全部 (1) 進行管理，以方便用戶、提高計算機使用效率的一種系統(tǒng)軟件。它的主要功能有：處理機管理、存儲管理、文件管理、 (2) 管理和設備管理等。Windows和Unix是最常用的兩類操作系統(tǒng)。前者是一個具有圖形界面的窗口式的 (3) 系統(tǒng)軟件，后者是一個基本上采用 (4) 語言編制而成的的系統(tǒng)軟件。在 (5) 操作系統(tǒng)控制下，

27、計算機能及時處理由過程控制反饋的信息并作出響應。供選答案：(1):A. 應用軟件B. 系統(tǒng)軟硬件C. 資源D. 設備(2):A. 數(shù)據(jù)B. 作業(yè)C. 中斷D. I/O(3):A. 分時B. 多任務C. 多用戶D. 實時(4):A. PASCALB. 宏C. 匯編D. C(5):A. 網絡B. 分時C. 批處理D. 實時答案：CBBDD43.本程序從鍵盤讀入整數(shù)，并按從大到小的順序輸出輸入整數(shù)中互不相等的那些整數(shù)。程序一邊讀入整數(shù)，一邊構造一個從大到小順序鏈接的鏈表，直至不能從鍵盤讀入整數(shù)，然后順序輸出鏈表上各表元的整數(shù)值。主函數(shù)每讀入一個整數(shù)，就調用函數(shù)insert()，函數(shù)insert()將

28、還未出現(xiàn)在鏈表上的整數(shù)按從大到小的順序插入到鏈表中。為了插入方便，鏈表在表首有一個輔助表元。閱讀下列C代碼，在 (n) 處填入相應的字句以完成上述功能。#include <stdio.h>#include <malloc.h>#define NULL 0typedef struct nodeint val;struct node *next;NODE;void insert(NODE *list,int x)NODE *u, *v, *p;u = list; v = u->next;while( (1) && x < v->val)/*

29、尋找插入位置*/u=v;v=u->next;if(v=NULL | (2) )/*判斷是否要插入表元*/p = (NODE *)malloc(sizeof(NODE);p->val = x;/*生成新表元*/ (3) = v; (4) = p;/*插入新表元*/main()int x;NODE *head, *p;/*首先建立只有輔助表元的空鏈表*/head = (NODE *)malloc(sizeof(NODE); (5) =NULL;printf(“Enter Integers:n”);while(scanf(“%d”,&x) = 1)/*反復讀入整數(shù)插入鏈表*/in

30、sert(head,x);for(p=head->next;p!=NULL;p=p->next)/*輸出鏈表*/printf(“%dt”,p->val);printf(“n”);答案：(1) v != NULL或v(2) x > v->val 或 x != v->val(3) p->next(4) u->next(5) head->next44.計算機數(shù)據(jù)處理的對象是具有不同結構的各種數(shù)據(jù)，可以訪問的最小數(shù)據(jù)信息單位是 (1) ，可以引用的最小命名數(shù)據(jù)單位是 (2) 。線性表是最簡單的一種數(shù)據(jù)結構，有順序和鏈接兩種存儲方式。線性表按鏈接方式

31、存儲時，每個結點的包括 (3) 兩部分。線性表的查找有 (4) 和 (5) 兩種，但 (5) 只能用于順序存儲的情況。供選答案：(1):A. 數(shù)字B. 字符C. 數(shù)據(jù)元素D. 數(shù)據(jù)項(2):A. 結點B. 記錄C. 數(shù)據(jù)元素D. 數(shù)據(jù)項(3):A. 數(shù)據(jù)值與符號B. 數(shù)據(jù)與指針C. 數(shù)據(jù)與表名D. 頭地址與尾地址(4):A. 隨機查找B. 順序查找C. 二分法查找D. 瀏覽(5):A. 隨機查找B. 順序查找C. 二分法查找D. 瀏覽答案：CDBBC45.本程序用于從鏈盤讀入整數(shù)，插入到鏈表，或從鏈表刪除一個整數(shù)。閱讀下面的C代碼，將應填入 (n) 處的字名寫在答卷的對應欄內。#include

32、 <stdio.h>#include <malloc.h>typedef struct nodeint val;struct node * next;NODE;NODE * ins(NODE *list, int x)/*將x按從小到大的次序插入鏈表*/NODE *u, *v=list, *p;for(; v != NULL && x < v->val ; v = v->next);/*尋找插入位置*/if(v != NULL && x = v->val) return(list); /*已有，被忽略*/p = (

33、NODE *)malloc(sizeof(NODE);p->val=x; /*生成新表元*/if(v = list) list = p;else (1) ; (2) ;return list;NODE * del(NODE * list, int x)/*從鏈表中刪除值為x的表元*/NODE *u, *v;for(v = list; v != NULL && x < v->valu; u=v;v=v->next);if(v != NULL && x = v->val)/*找到值為x的表元*/if(v = list)list = li

34、st->next;else (3) ; (4) ;/*釋放空間*/elseprintf(“沒有找到!n”);return(list);main()int x,ans;NODE * list=NULL, *p;while(1)printf(“n輸入1：將整數(shù)插入到鏈表。n輸入2：從鏈表刪除一個整數(shù)。n”);printf(“其它整數(shù)，結束程序。nt請輸入選擇！”);scanf(%d,&ans);if( (5) )return;printf(“輸入整數(shù)：”);scanf(“%d”,&x);if(ans=1)list=ins(list,x);elselist=del(list,x

35、);for(p=list;p!=NULL;p=p->next)printf(“%4d”,p->val);答案：(1) u->next = p;(2) p->next = v(3) u->next = v->next(4) free(v)(5) ans != 1 && ans != 246. 從未排序的序列中，依次取出元素，與已排序序列的元素比較后，放入已排序序列中的恰當位置上，這是 (1) 排序。從未排序的序列中，挑選出元素，放在已排序序列的某一端位置，這是 (2) 排序。逐次將待排序的序列中的相鄰元素兩兩比較，凡是逆序則進行交換，這是 (3

36、) 排序。如果整個排序過程都在內存中進行，稱為 (4) 排序。排序算法的復雜性與排序算法的 (5) 有關。供選答案：(1):A. 選擇B. 插入C. 比較D. 歸并(2):A. 選擇B. 插入C. 比較D. 歸并(3):A. 冒泡B. 交換C. 比較D. 散列(4):A. 外部B. 內部C. 外存D. 內存(5):A. 運算量大小與占用存儲多少B. 運算量大小與處理的數(shù)據(jù)量大小C. 并行處理能力和占用存儲多少D. 占用存儲多少和處理的數(shù)據(jù)量大小答案：BAABA47.操作系統(tǒng)是對計算機資源進行的 (1) 系統(tǒng)軟件，是 (2) 的接口。在處理機管理中，進程是一個重要的概念，它由程序塊、 (3) 和

37、數(shù)據(jù)塊三部分組成，它有3種基本狀態(tài)，不可能發(fā)生的狀態(tài)轉換是 (4) 。虛擬存儲器的作用是允許程序直接訪問比內存更大的地址空間，它通常使用 (5) 作為它的一個主要組成部分。供選答案：(1):A. 輸入和輸出B. 鍵盤操作C. 管理和控制D. 匯編和執(zhí)行(2):A. 軟件和硬件B. 主機和外設C. 高級語言和機器語言D. 用戶和計算機(3):A. 進程控制塊B. 作業(yè)控制塊C. 文件控制塊D. 設備控制塊(4):A. 運行態(tài)轉換為就緒態(tài)B. 就緒態(tài)轉換為運行態(tài)C. 運行態(tài)轉換為等待態(tài)D. 等待態(tài)轉換為運行態(tài)(5):A. 軟盤B. 硬盤C. CDROMD. 寄存器答案：CDADB48. A 是信息

38、的載體，它能夠被計算機識別、存儲和加工處理。A. 數(shù)據(jù)B. 數(shù)據(jù)元素C. 結點D. 數(shù)據(jù)項49.下列程序段的時間復雜度為 C 。for(i=1;i<n;i+)y=y+1;for(j=0;j<=(2*n);j+)x+;供選答案：A. O(n-1)B. O(2n)C. O(n2)D. O(2n+1)50.下面程序段的時間復雜度為 D 。i=1;while(i<=n)i=i*2;供選答案：A. O(1)B. O(n)C. O(n2)D. O(log2n)51.下面程序段的時間復雜度為 B 。a=0;b=1;for(i=2;i<=n;i+)s=a+b;b=a;a=s;供選答案：

39、A. O(1)B. O(n)C. O(log2n)D. O(n2)52.數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中，計算機的 A 以及它們之間的關系和運算等的學科。A.操作對象B. 計算方法C. 邏輯存儲D. 數(shù)據(jù)映象53.在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成 C 。A. 動態(tài)結構和靜態(tài)結構B. 緊湊結構和非緊湊結構C. 線性結構和非線性結構D. 內部結構和外部結構54.算法分析的目的是 C 。A. 找出數(shù)據(jù)結構的合理性B. 研究算法中輸入和輸出的關系C. 分析算法的效率以求改進D. 分析算法的易懂性和文檔性55.算法分析的兩個主要方面是 (4) 。A. 間復雜性和時間復雜性B. 正確性

40、和簡明性C. 可讀性和文檔性D. 數(shù)據(jù)復雜性和程序復雜性56.一個線性順序表第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址為 B 。A. 110B. 108C. 100D. 12057.若已知一個棧的入棧序列是1,2,3,n，其輸出序列為P1,P2,P3,Pn，若P1=n，則Pi為 C 。A. iB. n-iC. n-i+1D.不確定58.對于一個棧，給出輸入項A,B,C。如果輸入項序列由A,B,C所組成，則不可能產生的輸出序列是 A 。A. CABB. CBAC. ABCD. ACB59.設有如下的單鏈表的按序號查找的算法，其時間復雜度為 B 。LinkNode *Ge

41、tNode(Linklist head, int i)int j;ListNode *p;P = head; j=0;while(p->next && j<i)p = p->next;j+;if(i=j)return(p);elsereturn(NULL);供選答案：A. O(n2)B. O(2n)C. O(n3)D. O(logn)60.二維數(shù)組Amn按行序為主順序存放在內存中，每個數(shù)組元素占1個存儲單元，則元素aij的地址計算公式是 C 。A. LOC(aij) = LOC(a11)+(i-1)*m+(j-1)B. LOC(aij) = LOC(a11)+

42、(j-1)*m+(i-1)C. LOC(aij) = LOC(a11)+(i-1)*n+(j-1)D. LOC(aij) = LOC(a11)+(j-1)*n+(i-1)61.以下哪一個不是隊列的基本運算 C 。A. 從隊尾插入一個新元素B. 從隊列中刪除第i個元素C. 判斷一個隊列是否為空D. 讀取隊頭元素的值62.在一個長度為n的順序表中，向第i個元素之前插入一個新元素，需向后移動 B 個元素。A. n-iB. n-i+1C. n-i-1D. i63.從一個長度為n的順序表中刪除第i個元素時，需向前移動 A 個元素。A. n-iB. n-i+1C. n-i-1D. i64.在具有n個單元的

43、順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針，則判斷隊空的條件是 B 。A. front=rear+1B. front=rearC. front+1=rearD. front=065.從一個具有n個結點的單鏈表中查找其值等于x的結點時，在查找成功的情況下，需平均比較 D 個結點。A. nB. n/2C. (n-1)/2D. (n+1)/266.一個棧的入棧序列是a,b,c,d,e，則棧不可能的輸出序列是 C 。A. edcbaB. decbaC. dceabD. abcde67.棧結構通常采用的兩種存儲結構是 A 。A. 順序存儲結構和鏈表存儲結構B. 散列方式和索引

44、方式C. 鏈表存儲結構和數(shù)組D. 線性存儲結構和非線性存儲結構68.判斷一個順序棧ST（最多元素為mo）為空的條件是 B 。A. ST->top<>0B. ST->top=0C. st->top<>moD. st->top=mo69.不帶頭結點的單鏈表head為空表的判定條件是 A 。A. head=NILLB. head->next=NULLC. head->next=headD. head != NULL70.在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在p和q之間插入s結點，則應執(zhí)行 C 。A. s->next

45、 = p->next; p->next=s;B. p->next = s->next; s->next=p;C. q->next = s; s->next=p;D. p->next = s; s->next=q;71.假設雙向鏈表結點的類型如下：typedef struct Linknodeint data;struct Linknode *lLink;/*前驅結點指針*/struct Linknode *rLink;/*后繼結點指針*/下面給出的算法是要把一個q所指新結點，作為非空雙向鏈表中的p所指的結點前驅結點插入到該雙向鏈表中，能正確

46、完成要求的算法段是 C 。Aq->rLink=p; q->lLink=p->lLink; p->lLink=q; p->lLink->rLink=q;B. p->lLink=q, q->rLink=p; p->lLink->rLink=q; q->lLink=p->lLink;C. q->lLink=p->lLink; q->rLink=p;p->lLink->rLink=q;p->lLink=q;D. 以上均不對72.串是一種特殊的線性表，其特殊性體現(xiàn)在 B 。A. 可以順序存儲B.

47、數(shù)據(jù)元素是一個字符C. 可以鏈接存儲D. 數(shù)據(jù)元素可以是多個字符73.設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作 B 。A. 連接B. 模式匹配C. 求子串D. 求串長74.設串s1=”ABCDEFG”，s2=”PQRST”，函數(shù)con(x,y)返回x和y串的連接串，subs(s,I,j)返回串s的從序號i的字符開始的j個字符組成的子串，len(s)返回串s的長度，則con(sub(s1,2,len(s2),sub(s1,len(s2),2)的結果是 D 。A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF75.常對數(shù)組進行的兩種基本操作是 C 。A. 建立和

48、刪除B. 索引和修改C. 查找和修改D. 索引和查找76.稀疏矩陣一般的壓縮存儲方法有兩種，即 。A. 二維數(shù)組和三維數(shù)組B. 三元組和散列C. 三元組和十字鏈表D. 散列和十字鏈表77.對下圖所示的二叉表，按先根次序遍歷得到的結點序列為 B 。A. ABCDHEIFGB. ABDHIECFGC. HDIBRAFCGD. HIDBEFGAC78.在一棵二叉樹上，度為0的結點個數(shù)為n0，度為2的結點數(shù)為n2，則n0= A 。A. n2+1B. n2-1C. n2D. n2/279.某二叉樹前序遍歷結點的訪問順序是ABCDEFG，中序遍歷結點的訪問順序是CBDAFGE，則其后序遍歷結點的訪問順序是 A 。ACDBGFEAB. CDGFEABC. CDBAGFED. CDB