數(shù)據(jù)結(jié)構(gòu)形考2，國開網(wǎng)
形考作業(yè)2
一、單項選擇題（每小題2分，共50分）
1.若讓元素1，2，3依次進棧，則出棧順序不可能為（ ）。
A.3，2，1 B.2，1，3 C.3，1，2 D.1，3，2
答案：C
2.一個隊列的入隊序列是1，2，3，4。則隊列的輸出序列是（ ）。
A.4，3，2，1 B.1，2，3，4 C.1，4，3，2 D.3，2，4，1
答案：B
3.向順序棧中壓入新元素時，應(yīng)當（ ）。
A.先移動棧頂指針，再存入元素 B.先存入元素，再移動棧頂指針 C.先后次序無關(guān)緊要 D.同時進行
答案：A
4.在一個棧頂指針為top的鏈棧中，將一個p指針所指的結(jié)點入棧，應(yīng)執(zhí)行（ ）。
A.top->next=p; B.p->next=top->next;top->next=p; C.p->next=top;top=p; D.p->next=top->next;top=top->next;
答案：C
5.在一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用 x保存被刪結(jié)點的值，則執(zhí)行（ ）。
A.x=top;top=top->next; B.x=top->data; C.top=top->next;x=top->data; D.x=top->data;top=top->next;
答案：D
6.判斷一個順序隊列（最多元素為m）為空的條件是（ ）。
A.rear==m-1 B.front==rear C.rear=m D.front==rear+1
答案：B
7.判斷一個循環(huán)隊列為滿的條件是（ ）。
A.rear=MaxSize B.front==rear+1 C.(rear+1)%MaxSize==front ?D.rear%MaxSize= =front
答案：C
8.判斷棧滿（元素個數(shù)最多n個）的條件是（ ）。
A.top==0 B.top!=0 C.top==n-1 D.top=-1
答案：C
9.設(shè)有一個20階的對稱矩陣A（第一個元素為a1,1），采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始）， 則矩陣元素a6,2在一維數(shù)組B中的下標是（ ）。
A.21 B.17 C.28 D.23
答案：B
10.在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個（ ）結(jié)構(gòu)。
A.堆棧 B.隊列 C.數(shù)組 D.線性表
答案：B
11.一個遞歸算法必須包括（ ）。
A.遞歸部分 B.終止條件和遞歸部分 C.迭代部分 D.終止條件和迭代部分
答案：B
12.在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運算為（ ）。
A.r=f->next; B.r=r->next; C.f=f->next; D.f=r->next;
答案：C
13.在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的運算為（ ）。
A.f->next=s;f=s; B.r->next=s;r=s; C.s->next=r;r=s; D.s->next=f;f=s;
答案：B
14.數(shù)組a經(jīng)初始化char a[ ]=“English”;a[7]中存放的是（ ）。
A.字符串的結(jié)束符 B.字符h C."h" D.變量h
答案：A
15.設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（ ）。
A.Bcd B.BCd C.ABC D.Abc
答案：A
16.字符串 a1="AEIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（ ）。
A.a1 B.a2 C.a3 D.a4
答案：A
17.兩個字符串相等的條件是（ ）。
A.兩串的長度相等 B.兩串包含的字符相同 C.兩串的長度相等，并且兩串包含的字符相同 D.兩串的長度相等，并且對應(yīng)位置上的字符相同
答案：D
18.一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用6個字節(jié)，第6個元素的存儲地址為100，則該數(shù)組的首地址是（ ）。
A.64 B.28 C.70 D.90
答案：C
19.一個非空廣義表的表頭（ ）。
A.不可能是原子 B.只能是子表 C.只能是原子 D.可以是子表或原子
答案：D
20.對稀疏矩陣進行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A，其相應(yīng)的三元組表共有6個元素，矩陣A共有（ ）個零元素。
A.8 B.72 C.74 D.10
答案：C
21.對稀疏矩陣進行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A共有73個零元素，A的右下角元素為6，其相應(yīng)的三元組表中的第7個元素是（ ）。
A.（10，8，6） B.（10，8，7） C.（7，10，8） D.（7，8，10）
答案：A
22.對一個棧頂指針為top的鏈棧進行入棧操作，通過指針變量p生成入棧結(jié)點，并給該 結(jié)點賦值a，則執(zhí)行: p=(struct node *)malloc(sizeof(struct node);p->data=a;和（ ）。
A.p->next=top;top=p; B.top->next=p;p=top; C.top=top->next;p=top; D.p->next=top;p=top;
答案：A
23.頭指針為head的帶頭結(jié)點的單向鏈表為空的判定條件是（ ）為真。
A.head==NULL B.head->next!=NULL C.head->next==NULL D.head->next!=NULL
答案：C
24.設(shè)有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），B數(shù)組共有55個元素,則該矩陣是（ ）階的對稱矩陣。
A.5 B.20 C.10 D.15
答案：C
25.數(shù)組a經(jīng)初始化char a[ ]=“English”;a[1]中存放的是（ ）。
A.字符n B.字符E C."n" D."E"
答案：A
二、判斷題（每小題2分，16題，共32分 ）
26.設(shè)有一個鏈棧，棧頂指針為hs，現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作。hs=s；
s-> next=hs;
答案：錯
27.設(shè)有一個非空的鏈棧，棧頂指針為hs，要進行出棧操作，用x保存出棧結(jié)點的值，棧
結(jié)點的指針域為next，則可執(zhí)行hs=hs->next ;x=hs->data;
答案：錯
28.有一個鏈棧，棧頂指針為h，現(xiàn)有一個p所指向的結(jié)點要入棧，則可執(zhí)行操作p->next=h;
和h=p；
答案：對
29. 設(shè)有一個非空的鏈棧，棧頂指針為hs，要進行出棧操作，用x保存出棧結(jié)點的值，棧結(jié)點的指針域為next，數(shù)據(jù)域為data，則可執(zhí)行hs= hs->next; x= hs->data;
答案：錯
30. 在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next，則插入所指結(jié)點的操作為r->next=s；r=s；
答案：對
31. 在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next，s指向一個要入 隊的結(jié)點，則入隊操作為r=s；r->next=s；
答案：錯
32. 在一個不帶頭結(jié)點的非空鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的數(shù)據(jù)域為data，指針域為next，若要進行出隊操作，并用變量x存放出隊元素的數(shù)據(jù)值，則相關(guān)操作為x=f->data; f=f->next;
答案：對
33.對稀疏矩陣進行壓縮存儲,可采用三元組表，一個6行7列的稀疏矩陣A相應(yīng)的三元組表共有8個元素,則矩陣A共有34個零元素。
答案：對
34. 循環(huán)隊列的最大存儲空間為MaxSize，隊頭指針為f，隊尾指針為r，當（r+1）%MaxSize=f 時表明隊列已滿。
答案：對
35.循環(huán)隊列的隊頭指針為f，隊尾指針為r，當r= =f時表明隊列已滿。
答案：錯
36.空串的長度是0；空格串的長度是空格字符的個數(shù)。
答案：對
37. 對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的行下標、列下標、和非零元素值三項信息。
答案：對
38.循環(huán)隊列的引入，目的是為了克服假上溢。
答案：對
39.設(shè)有n階對稱矩陣A，用一維數(shù)組s壓縮存儲A的下三角元素，s的下標從零開始，元素 s[26]相應(yīng)于A中的元素為a 7,5。
答案：錯
40. 循環(huán)隊列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針front=4，當隊尾指針rear=3時隊滿。
答案：對
41. 循環(huán)隊列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針front=4，隊尾指針rear=3時，隊列中共有5個元素。
答案：對
三、程序選擇填空題（每小題9分，共18分。請點擊正確選項，然后拖拽至相應(yīng)的方框上）
42.以下函數(shù)為鏈棧的進棧操作，x是要進棧的結(jié)點的數(shù)據(jù)域，top為棧頂指針
struct node
{ ElemType data;
struct node *next;
};
struct node *top ;
void Push(ElemType x)
{
struct node *p;
p=(struct node*)malloc __sizeof (struct node)__;
p->data=x;
__p->next=top__;
__top=p_;
}
43.以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別鏈隊列的隊頭、隊尾指針
struct node
{ ElemType data;
struct node *next;
};
struct node *front，*rear;
void InQueue(ElemType x)
{
struct node *p;
p= (struct node*) malloc _sizeof (struct node)__;
p->data=x;
p->next=NULL;
_rear->next=p_;
rear= __p__;
}
?
?
