嵌入式系統(tǒng)開發(fā)人員C語(yǔ)言測(cè)試題-數(shù)據(jù)結(jié)構(gòu)與算法.doc

11.1 選擇題 （833） 下面關(guān)于算法說法錯(cuò)誤的是_。 a. 算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn) b. 為解決某問題的算法同為該問題編寫的程序含義是相同的 c. 算法的可行性是指指令不能有二義性 d. 以上幾個(gè)都是錯(cuò)誤的 （834） 下面說法錯(cuò)誤的是_. a. 算法原地工作的含義是指不需要任何額外的輔助空間 b. 在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法 c. 所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界 d. 同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低 （835） 在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為_。 for (int i; in; i+) for (int j=o; jLlink=q; q-Rlink=p; p-Llink-Rlink=q; q-Llink=q； b. p-Llink=q; p-Llink-Rlink=q; q-Rlink=p; q-Llink=p-Llink; c. q-Rlink=p; q-Llink=p-Llink; p-Llink-Rlink=q; p-Llink=q; d. q-Llink=p-Llink; q-Rlink=q; p-Llink=q; p-Llink=q; （845） 下面說法正確的是_。 a. 順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作； b. 線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的； c. 順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好； d. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。 （846） 下面說法正確的是_。 a. 線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。 b. 為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。 c. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。 d. 鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序存儲(chǔ)結(jié)構(gòu)中效率高。 （847） 下面說法正確的是_。 a. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 b. 隊(duì)列邏輯上是一個(gè)下端口和上端能增加又能減少的線性表。 c. 任何一個(gè)遞歸過程都可以轉(zhuǎn)換成非遞歸過程。 d. 只有那種使用了局部變量的遞歸過程在轉(zhuǎn)換成非遞歸過程時(shí)才必須使用棧。 （848） 下面說法正確的是_。 a. 數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對(duì)它進(jìn)行插入、刪除等操作。 b. 兩分法插入排序所需比較次數(shù)與待排序記錄的初始排列狀態(tài)相關(guān)。 c. 當(dāng)待排序記錄已經(jīng)從小到大排序或者已經(jīng)從大到小排序時(shí)，快速排序的執(zhí)行時(shí)間最省。 d. 在索引順序表中，實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長(zhǎng)度不僅與表中元素個(gè)數(shù)有關(guān)，而且與每塊中元素個(gè)數(shù)有關(guān)。 （849） 下面說法正確的是_。 a. 在執(zhí)行某個(gè)排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列相反方向移動(dòng)，則該算法是不穩(wěn)定的。 b. 堆排序是穩(wěn)定的排序方法。 c. 在分配排序時(shí)，最高位優(yōu)先分配法比最低位優(yōu)先分配法簡(jiǎn)單。 d. 最佳兩叉排序樹的任何子樹都是最佳的。 （850） 具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度是：_。 a. log2n b.LOG2N/1 c. LOG2(N/1) d.LOG2N-1 （851） 用單循環(huán)鏈表表示隊(duì)列，正確的說法是：_。 a. 可設(shè)一個(gè)頭指針使入隊(duì)、出隊(duì)都方便 b. 可設(shè)一個(gè)尾指針使入隊(duì)、出隊(duì)都方便 c. 必須設(shè)頭尾指針才能使入隊(duì)、出隊(duì)都方便 d. 無(wú)論如何,只可能使入隊(duì)方便 （852） 一個(gè)哈希函數(shù)被認(rèn)為是好的，如果它滿足條件_。 a. 哈希地址分布均勻 b. 保證不產(chǎn)生沖突 c. 所有哈希地址在表長(zhǎng)范圍內(nèi) d. 滿足(2)和(3) （853） ISAM文件和VSAM文件屬于_。 a. 索引非排序文件 b. 索引順序文件 c. 順序文件 d. 散列文件 （854） 在下述排序算法中_算法是穩(wěn)定的排序算法。 a. 希爾排序 b. 快速排序 c. 冒泡排序 d. 堆排序 （855） 在下述三種排序算法中，所需輔助存儲(chǔ)量最多的是_，所需存儲(chǔ)量最少的是_，平均速度最快的是_。 a. 堆排列 b. 快速排列 c.歸并排列 （856） 存貯稀疏圖的數(shù)據(jù)結(jié)構(gòu)常有的是_。 a. 鄰接矩陣 b. 三元組 c. 鄰接表 d. 十字鏈表 （857） 內(nèi)部排序多個(gè)關(guān)鍵字的文件，最壞情況下最快的排列方法是_,相應(yīng)的時(shí)間復(fù)雜度為_,該算法是的穩(wěn)定性_。 a. 快速排序 b. 插入排序 c. 歸并排序 d. 簡(jiǎn)單選擇排序 e. O(nlog2(n) f. O(n2) g. O(n2log2(n) h. O(n) i. 穩(wěn)定 j. 不穩(wěn)定 （858） 倒排文件包含若干個(gè)倒排表，倒排表的內(nèi)容是_。 a. 一個(gè)關(guān)鍵字值和關(guān)鍵字的記錄地址； b. 一個(gè)屬性值和該屬性的一個(gè)記錄地址； c. 一個(gè)屬性值和該屬性的全部屬性地址； d. 多個(gè)關(guān)鍵字值和它們對(duì)應(yīng)的某個(gè)記錄的地址。 （859） 在下述幾種樹當(dāng)中,_可以表示靜態(tài)查找表. a. 次優(yōu)查找樹; b. 二叉排序樹; c. B-樹 d. 平衡二叉樹 （860） 選擇填空： (1). 在文件局部有序或文件長(zhǎng)度較小的情況下,最優(yōu)內(nèi)部排序的方法是_. (2). 快速排序在最壞的情況下,時(shí)間復(fù)雜度是_,_的性能差; (3). 就平均時(shí)間而言,_最佳. a.: (1)直接插入排序 (2)起泡排序 (3)簡(jiǎn)單選擇排序; b.: (1)O(nlog(n) (2)O(n2) (3)O(n3) c.: (1)堆排序 (2)起泡排序 (3)選擇排序. d.: (1)堆排序 (2)快速排序 (3) 歸并排序. （861） 算法的時(shí)間復(fù)雜度取決于_。 a. 問題的規(guī)模 b. 待處理數(shù)據(jù)的初態(tài) c. both a and b （862） 假定有k個(gè)關(guān)鍵字互為同義詞,若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中,至少要進(jìn)行_次探測(cè)。 a. k-1 b. k c. k=1 d. k(k+1)/2 （863） 若需要在O(nlog2(n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序,且要求排序是穩(wěn)定的,則可選擇的排序方法是: a. 快速排序 b. 堆排序 c. 歸并排序 d. 直接插入排序 （864） 將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表,其最少的比較次數(shù)是_。 a. n b. 2n-1 c. 2n d. n-1 （865） 下述二叉樹中,_滿足性質(zhì):從任意結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序。 a. 二叉排序樹 b. 哈夫曼樹 c. AVL樹 d. 堆 （866） 若在線性表中采用折半查找法查找元素，該線性表應(yīng)該_。 a. 元素按值有序 b. 采用順序存儲(chǔ)結(jié)構(gòu) c. 元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu) d. 元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) （867） 若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左右子樹的位置，利用_遍歷方法最合適。 a. 前序 b.中序 c.后序 d. 按層次 （868） 對(duì)二叉排序樹進(jìn)行_遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的排序序列。 a. 前序 b. 中序 c.后序 d. 按層次 （869） 從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為_排序法。 a. 插入 b. 選擇 c. 謝爾 d. 二路歸并 （870） 排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是_排序法。 a. 插入 b. 選擇 c. 泡 d. 快速 （871） 下面給出的四種排序法中_排序法是不穩(wěn)定性排序法。 a. 插入 b. 泡 c. 二路歸并 d. 堆積 （872） 下面哪一個(gè)方法可以判斷出一個(gè)有向圖中是否有環(huán)（回路）？ a. 深度優(yōu)先遍歷 b. 拓樸排序 c. 求最短路徑 d. 求關(guān)鍵路徑 （873） 下面關(guān)于程序設(shè)計(jì)風(fēng)格的說法正確的是_。 a. 中序遍歷一棵二叉排序樹的節(jié)點(diǎn)就可得到排好序的節(jié)點(diǎn)序列。 b. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。 c. 順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈接存儲(chǔ)的線性表。 d. 棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。 （874） 已知變量定義： char S3=AB char *P; 在執(zhí)行了語(yǔ)句PS之后，*（P2）的值是_。 a. B b. 0 c. 不確定 d. 字符B的地址 （875） 下面程序段的時(shí)間復(fù)雜度為_。 for(int i=0;im;i+) for(int j=0;j=MAX_STACK_SIZE-1) return stack_full(); stack =item; 則在stack 的中括號(hào)內(nèi)橫線上的正確內(nèi)容應(yīng)為：_。 a. +*top b. *top+ c. *top- d. *top （877） 有如下函數(shù)： void fun(struct node h1,struct node h2) struct node *t; t=h1; while (t-next != 0) t = t-next; t-next = h2; 其中形參h1和h2分別指向2個(gè)不同鏈表的第一個(gè)結(jié)點(diǎn)，此函數(shù)的功能是：_。 a. 將鏈表h2接到鏈表h1后 b. 將鏈表h1接到鏈表h2后 c. 找到鏈表h1的最后一個(gè)結(jié)點(diǎn)由指針返回 d. 將鏈表h1拆分成兩個(gè)鏈表 （878） 一個(gè)棧的入棧序列是abcde，則棧的不可能輸出序列是： _。 a. edcba b. decba c. dceab d. abcde （879） 下面說法正確的是_。 a. 隊(duì)列邏輯上是一個(gè)表頭和表尾既能插入又能刪除的線性表。 b. 任何一個(gè)遞歸過程都可以轉(zhuǎn)換成非遞歸過程。 c. 與n個(gè)鍵值的集合k1,k2,kn相對(duì)應(yīng)的堆是唯一的。 d. 在索引順序表上實(shí)現(xiàn)分塊查找，在等概率查找情況下，其查找長(zhǎng)度只與表中元素個(gè)數(shù)有關(guān)，而與每塊中元素個(gè)數(shù)無(wú)關(guān)。 （880） 下面說法正確的是_。 a. 在10萬(wàn)個(gè)隨機(jī)排列的數(shù)據(jù)中，要選出5個(gè)最小的數(shù)，采用快速排序比采用Shell排序、堆排序及各種直接排序法都快。 b. 哈希表查找無(wú)需進(jìn)行關(guān)鍵字的比較。 c. 在執(zhí)行某個(gè)排序過程中，出現(xiàn)排序碼朝著最終位置相反方向移動(dòng)，則該算法是不穩(wěn)定的。 d. B樹查找算法的時(shí)間復(fù)雜性為O（n）。 （881） 下列有關(guān)線性表的敘述中，正確的是_。 a. 線性表中的元素之間隔是線性關(guān)系 b. 線性表中至少有一個(gè)元素 c. 線性表中任何一個(gè)元素有且僅有一個(gè)直接前趨 d. 線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼 （882） 下列關(guān)于串的敘述中，正確的是_。 a. 一個(gè)串的字符個(gè)數(shù)即該串的長(zhǎng)度 b. 一個(gè)串的長(zhǎng)度至少是1 c. 空串是由一個(gè)空格字符組成的串 d. 兩個(gè)串S1和S2若長(zhǎng)度相同，則這兩個(gè)串相等 （883） 4個(gè)元素a1，a2，a3和a4依次通過一個(gè)棧，在a4進(jìn)棧前，棧的狀態(tài)是_。 不可能的出棧序是_。 a. a4，a3，a2，a1 b. a3，a2，a4，a1 c. a3，a1，a4，a2 d. a3，a4，a2，a1 （884） 以數(shù)組Q0.m1存放循環(huán)隊(duì)列中的元素，變量rear和qulen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的實(shí)際位置和當(dāng)前隊(duì)列中元素的個(gè)數(shù)，隊(duì)列第一個(gè)元素的實(shí)際位置是_。 a. rearqulen b. rearqulenm c. mqulen d. 1（rearmqulen）mod m （885） 高二叉樹根結(jié)點(diǎn)的層次為1，所有含有15個(gè)結(jié)點(diǎn)的二叉樹中，最小高度是_。 a. 6 b. 5 c. 4 d. 3 （886） 下列四種排序方法中，不穩(wěn)定的方法是_。 a. 直接插入排序 b. 冒泡排序 c. 歸并排序 d. 直接選擇排序 （887） 設(shè)有一個(gè)長(zhǎng)度為100的已排好序的表，用二分查找進(jìn)行查找，若查找不成功，至少比較_次。 a. 9 b. 8 c. 7 d. 6 （888） 一棵二叉排序樹T，用_方法進(jìn)行遍歷，可以得到各結(jié)點(diǎn)鍵值的遞增序列。 a. 先根遍歷 b. 中根遍歷 c. 層次遍歷 d. 后根遍歷 （889） 設(shè)結(jié)點(diǎn)x和結(jié)點(diǎn)y是二叉樹T中的任意兩個(gè)結(jié)點(diǎn)，若在先根序列中x在y之前，而在后根序列中x在y之后，則x和y的關(guān)系是_。 a. x是y的左兄弟 b. x是y的右兄弟 c. x是y的祖先 d. x是y的后代 （890） 下面說法正確的是_。 a. 數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 b. 線性表的鏈接存儲(chǔ)，表中元素的邏輯順序與物理順序一定相同。 c. 二叉樹中任何一個(gè)結(jié)點(diǎn)的度都是2。 d. 由二叉樹結(jié)點(diǎn)的先根序列的后根序列可以唯一地確定一棵二叉樹。 （891） 下面說法正確的是_。 a. 用直接選擇排序方法分別對(duì)序列S1（1，2，3，4，5，6，7）和序列S2（7，5，3，2，4，1，6）進(jìn)行排序，兩者的比較次數(shù)不相同。 b. 一棵哈夫曼樹中不存在度為1的結(jié)點(diǎn)。 c. 用二分查找法對(duì)一個(gè)順序表進(jìn)行查找，這個(gè)順序表可以是按各鍵值排好序的，也可以是沒有按鍵值排好序的。 d. 順序文件適宜順序存取，不適宜隨機(jī)存取。 （892） 下列算法中，某一輪結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是_。 a. 堆排序 b. 冒泡排序 c. 直接插入排序 d. 快速排序 （893） _是不穩(wěn)定的排序方法。 a. 冒泡排序 b. 歸并排序 c. 堆排序 d. 選擇排序 （894） 從邏輯上，可以將數(shù)據(jù)結(jié)構(gòu)分為_兩類。 a. 動(dòng)態(tài)表和靜態(tài)表 b. 順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu) c. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) d. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) 11.2 填空題 （895） 下面程序段的時(shí)間復(fù)雜度為_。 sum=1； for (i=0; sumn; i+) sum+=1; （896） 下列程序的功能是創(chuàng)建單向鏈表，請(qǐng)補(bǔ)充完整。 #include #include struct link char name10; int mark; struct link * next; ; void insert(char * name, int mark); struct link * head = NULL; main() char name10; int mark; struct link *t; while (1) scanf(%s %d, name, &mark); if (strcmp(name, #) = 0 ) break; _(1)_; for (t=head; _(2)_) printf(: %dn, t-name, t-mark); void insert(char * name, int mark) struct link * p; p = _(3)_ ; strcpy(p-name, name); p-mark = mark; _(4)_; if ( head != NULL ) _(5)_; head = p; （897） 用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n， 若只設(shè)頭指針,則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是_和_； 若只設(shè)尾指針,則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是_和_。 （898） 在n個(gè)記錄的有序順序表中進(jìn)行折半查找,最大的比較次數(shù)是_。 （899） 仔細(xì)閱讀下列程序，在空白處填入適當(dāng)?shù)恼Z(yǔ)句。 函數(shù)match(s,t)完成在字符串s中尋找與t匹配的字符，若存在一個(gè)匹配，則返回t在字符串s中的下標(biāo)；否則，返回-1。其中，字符指針*b始終指向s的第一元素。 Match(s,t) Char s,t; char *b=s; char *p, *r; for _ for (p=s, r=t; *r!=0 & *p= =*r; p+, r+); if_ return(s-b); return(-1); （900） 補(bǔ)充下列程序：設(shè)一棵二叉序列樹b，下列算法函數(shù)是實(shí)現(xiàn)在b中插入一個(gè)結(jié)點(diǎn)s。 函數(shù)： void insert（btree *b，btree *s） if（b = NULL） b = s； else if（s-data = b-data） return(); else if(s-data data) ； else ； （901） 一個(gè)nn的下三角矩陣A中的元素aij（ij，1i，jn）按行存于一個(gè)一維數(shù)組B1.n（n1）/2中，對(duì)其中的任一元素aij，若在B中的位置為k，則k_。 （902） 含有100個(gè)結(jié)點(diǎn)的樹有_條邊。 （903） 設(shè)一個(gè)閉散列表的容量為m，用線性控測(cè)法解決沖突，要插入一個(gè)鍵值，若插入成功，至多要進(jìn)行_次比較。 （904） 設(shè)二維數(shù)組M：array-1.4，0.3of integer，每個(gè)元素（整數(shù)）占個(gè)存儲(chǔ)單元，元素按行的順序存儲(chǔ)，數(shù)組的起始地址為200，元素M2，1的地址是_。 （905） 線性表L（a1，a2，.，an）采用順序存儲(chǔ)，假定在不同的n1個(gè)位置上插入的概率相同，則插入一個(gè)新元素平均需要移動(dòng)的元素個(gè)數(shù)是_。 （906） 設(shè)棧S和隊(duì)列Q的初始狀態(tài)皆為空，元素a1，a2，a3，a4，a5和a6依次通過一個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)列的順序是a3，a5，a4，a6，a2，a1則棧S至少應(yīng)該容納_個(gè)元素。 （907） 兩個(gè)序列如下： L1 25，57，48，37，92，86，12，33 L2 25，37，33，12，48，57，86，92 用冒泡排序方法分別對(duì)序列L1和L2進(jìn)行排序，交換次序較少的是序列_。 （908） 將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始，由根向下，每一層從左至右，順序地存儲(chǔ)在一個(gè)一維數(shù)組bt1.50中，這棵二叉樹最下面一層上最左邊一個(gè)結(jié)點(diǎn)存儲(chǔ)在數(shù)組元素_中。 （909） 一個(gè)索引文件由_兩部分組成。 11.3 問答與設(shè)計(jì) （910） 說明線性插入排序的算法及時(shí)間、空間復(fù)雜度 （911） 說明折半插入排序的算法及時(shí)間、空間復(fù)雜度 （912） 說明堆排序的算法及時(shí)間、空間復(fù)雜度 （913） 說明希爾排序的算法及時(shí)間、空間復(fù)雜度 （914） 說明快速排序的算法及時(shí)間、空間復(fù)雜度 （915） 說明基數(shù)排序的算法及時(shí)間、空間復(fù)雜度 （916） 說明交換排序的算法及時(shí)間、空間復(fù)雜度 （917） 說明選擇排序的算法及時(shí)間、空間復(fù)雜度 （918） 說明歸并排序的算法及時(shí)間、空間復(fù)雜度 （919） 說明分布排序的算法及時(shí)間、空間復(fù)雜度 （920） 說明順序查找的算法及時(shí)間、空間復(fù)雜度 （921） 說明折半查找的算法及時(shí)間、空間復(fù)雜度 （922） 說明分塊查找的算法及時(shí)間、空間復(fù)雜度 （923） 說明比較查找的算法及時(shí)間、空間復(fù)雜度 （924） 說明基數(shù)查找的算法及時(shí)間、空間復(fù)雜度 （925） 說明哈希查找的算法及時(shí)間、空間復(fù)雜度 （926） 怎樣查找鏈表中的數(shù)據(jù)? （927） 在一個(gè)包含 n 個(gè)元素的數(shù)組 M 中查找一個(gè)元素 x。 算法假設(shè) M 已經(jīng)按升序排列了，請(qǐng)寫出二分搜索算法的步驟。 （928） 已知鏈表節(jié)點(diǎn)的類型定義如下，需要按照成員value從小到大進(jìn)行排序，請(qǐng)寫出算法： #include #include typedef struct STRUCT int value; struct STRUCT *next; TS; （929） 什么是算法？算法的主要特點(diǎn)是什么？ （930） 如何評(píng)價(jià)一個(gè)算法？ （931） 什么是順序存儲(chǔ)結(jié)構(gòu)？什么是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)？ （932） 線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)各有什么特點(diǎn)？ （933） 若順序表A中的數(shù)據(jù)元素按升序排列，要求將x插入到順序表中的合適位置，以保證表的有序性，試給出其算法。 （934） 試將一個(gè)無(wú)序的線性表A=(11,16,8,5,14,10,38,23)轉(zhuǎn)換成一個(gè)按升序排列的有序線性表（用鏈表實(shí)現(xiàn)）。 （935） 簡(jiǎn)述棧和線性表的區(qū)別和聯(lián)系。 （936） 何為棧和隊(duì)列？簡(jiǎn)述兩者的區(qū)別和聯(lián)系。 （937） 若依次讀入數(shù)據(jù)元素序列a,b,c,d進(jìn)棧，進(jìn)棧過程中允許出棧,試寫出各種可能的出棧元素序列。 （938） 將下列各算術(shù)運(yùn)算式表示成波蘭式和逆波蘭式： (A*(B+C)+D)*E-F*G A*(B-D)+H/(D+E)-S/N*T (A-C)*(B+D)+(E-F)/(G+H) （939） 寫出算術(shù)運(yùn)算式3+4/25*8-6的操作數(shù)棧和運(yùn)算符棧的變化情況。 （940） 若堆棧采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，初始時(shí)為空，試畫出a,b,c,d四個(gè)元素依次進(jìn)棧后棧的狀態(tài)，然后再畫出此時(shí)的棧頂元素出棧后的狀態(tài)。 （941） 簡(jiǎn)述設(shè)計(jì)一個(gè)結(jié)點(diǎn)值為整數(shù)的循環(huán)隊(duì)列的構(gòu)思，并給出在隊(duì)列中插入或刪除一個(gè)結(jié)點(diǎn)的算法。 （942） 有一個(gè)循環(huán)隊(duì)列q(n)，進(jìn)隊(duì)和退隊(duì)指針分別為r和f；有一個(gè)有序線性表AM，請(qǐng)編一個(gè)把循環(huán)隊(duì)列中的數(shù)據(jù)逐個(gè)出隊(duì)并同時(shí)插入到線性表中的算法。若線性表滿則停止退隊(duì)并保證線性表的有序性。 （943） 設(shè)有棧stack，棧指針top=n-1，n0；有一個(gè)隊(duì)列Q(m)，其中進(jìn)隊(duì)指針r，試編寫一個(gè)從棧stack中逐個(gè)出棧并同時(shí)將出棧的元素進(jìn)隊(duì)的算法。 （944） 兩個(gè)字符串相等的充要條件是什么？ （945） 串有哪幾種存儲(chǔ)結(jié)構(gòu)？ （946） 設(shè)字符串采用塊鏈存儲(chǔ)結(jié)構(gòu)，塊鏈中每個(gè)結(jié)點(diǎn)存放m（m=4）個(gè)字符，試寫出實(shí)現(xiàn)字符串刪除的算法。 （947） 設(shè)s1和s2是用結(jié)點(diǎn)大小為1的單鏈表表示的串，試寫出找出s2中第一個(gè)不在s1中出現(xiàn)的字符的算法。 （948） 按行優(yōu)先存儲(chǔ)方式，寫出三維數(shù)組A324在內(nèi)存中的排列順序及地址計(jì)算公式（假設(shè)每個(gè)數(shù)組元素占用L個(gè)字節(jié)的內(nèi)存單元，a000的內(nèi)存地址為L(zhǎng)oc(a000)）。 （949） 按列優(yōu)先存儲(chǔ)方式，寫出三維數(shù)組A324在內(nèi)存中的排列順序及地址計(jì)算公式（假設(shè)每個(gè)數(shù)組元素占用L個(gè)字節(jié)的內(nèi)存單元，a000的內(nèi)存地址為L(zhǎng)oc(a000)）。. （950） 設(shè)有上三角矩陣Ann，它的下三角部分全為0，將其上三角元素按行優(yōu)先存儲(chǔ)方式存入數(shù)組Bm中(m足夠大)，使得Bk=aij，且有k=f1(i)+f2(j)+c。試推出函數(shù)f1、f2及常數(shù)c（要求f1和f2中不含常數(shù)項(xiàng)）。 （951） 若矩陣Amn中的某個(gè)元素Aij是第i行中的最小值，同時(shí)又是第j列中的最大值，則稱此元素為該矩陣中的一個(gè)馬鞍點(diǎn)。假設(shè)以二維數(shù)組存儲(chǔ)矩陣Amn，試編寫求出矩陣中所有馬鞍點(diǎn)的算法，并分析你的算法在最壞情況下的時(shí)間復(fù)雜度。 （952） 試寫一個(gè)算法，查找十字鏈表中某一非零元素x。 （953） 廣義表是線性結(jié)構(gòu)還是非線性結(jié)構(gòu)?為什么? （954） 畫出下列廣義表的圖形表示 (1) A(b,(A,a,C(A),C(A) (2) D(A( ),B(e),C(a,L(b,c,d) （955） 若邏輯結(jié)構(gòu)相同但存儲(chǔ)結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對(duì)嗎？舉例說明之。 （956） 在給定的邏輯結(jié)構(gòu)及其存儲(chǔ)表示上可以定義不同的運(yùn)算集合，從而得到不同的數(shù)據(jù)結(jié)構(gòu)。這樣說法對(duì)嗎？舉例說明之。 （957） 評(píng)價(jià)各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？ （958） 評(píng)價(jià)一個(gè)好的算法，需要從哪幾方面來考慮的？ （959） 什么是算法的時(shí)間復(fù)雜性？ （960） 什么是抽象數(shù)據(jù)類型？ （961） 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？ （962） 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)由哪四種基本的存儲(chǔ)方法實(shí)現(xiàn)？ （963） 運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。試舉一例，說明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同，只是對(duì)于運(yùn)算的定義不同。因而兩個(gè)結(jié)構(gòu)具有顯著不同的特性，是兩個(gè)不同的結(jié)構(gòu)。 （964） 在編制管理通訊錄的程序時(shí), 什么樣的數(shù)據(jù)結(jié)構(gòu)合適? 為什么? （965） 試舉一例，說明對(duì)相同的邏輯結(jié)構(gòu),同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，其運(yùn)算效率不同。 （966） 有實(shí)現(xiàn)同一功能的兩個(gè)算法A1和A2，其中A1的時(shí)間復(fù)雜度為Tl=O(2n)，A2的時(shí)間復(fù)雜度為T2=O(n2)，僅就時(shí)間復(fù)雜度而言，請(qǐng)具體分析這兩個(gè)算法哪一個(gè)好。 （967） 分析下面程序段中循環(huán)語(yǔ)句的執(zhí)行次數(shù)。 Int i= 0, s = 0, n = 100; Do i:=i+1; s:=s+10*i; while (In) & (sn) （968） 根據(jù)下面程序，回答下面問題： (1) 試指出f(n)值的大小，并寫出f(n) 值的推導(dǎo)過程; (2) 假定n= 5，試指出f(5)值的大小和執(zhí)行f(5)時(shí)的輸出結(jié)果。 int f(int n) int i, j, k, sum= 0; for(i=l; ii-1; j-) for(k=1; kj+1; k+ ) sum+; printf(sum=%dn, sum)； return (sum); （969） 設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。 int m = 0; For (int i = 0; i n; i+) for (int j = 2*i, j n; j+) m = m + 1; （970） 試給出下面兩個(gè)算法的運(yùn)算時(shí)間。 a. for (int I = 0; I n; I+) x+; b. for (int I = 1; I n; I+) for (int j = 1; j = (y+1)(y+1) y+; （988） 試舉例說明對(duì)相同的邏輯結(jié)構(gòu)，同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，其運(yùn)算效率不同。 （989） 對(duì)鏈表設(shè)置表頭結(jié)點(diǎn)的作用是什么？（至少說出2條好處） （