koorio.com
海量文库 文档专家
当前位置:首页 >> >>

数据结构习题(有答案)

资料

第1章 绪

1.1 有下列几种二元组表示的数据结构,试画出它们分别对应的图形表示, (1) 集合

并指出它们分别属于何种结构。 (1) A= ( D,R ),其中,D = { a1,a2,a 3,a4 }, R={ }

abc
(2) 线性表

(2) B= ( D,R ),其中,D = { a,b,c,d,e}, R={ (a,b),(b,c),

(c,d),(d,e)}

(3) C= ( D,R ),其中,D = { a,b,c,d,e,f,g}, R={ (d,b),(d,

d

g),(b,a),(b,c),(g,e),(e,f)}

b

g

(4) K= ( D,R ),其中,D = { 1,2,3,4,5,6}, R={ <1,2>,<2, 3>,<2,4>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>}

(3) 树

a

c

e

f

de
1
3
(4) 图

1.2 设 n 为正整数,求下列各程序段中的下划线语句的执行次数。

(1) i=1; k=0 while(i<=n-1) { k+=10*i ; i++;
}

(2) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) { c[i][j]=0; for (int k=1; k<=n; k++)
c[i][j]=c[i][j]+a[i][k]*b[k ][j] }

解: (1) n-1
nnn
(2) ???1 ? n3 i?1 j?1 k ?1

2
5 4
6

.

资料

(3) x=0; y=0; for (int i=1; i<=n; i++) for (int j=1; j<=i; j++) for (int k=1; k<=j; k++) x=x+y;

??? ?? ? ? ? n

i

j

n

1?

i j ? n i(i ?1) ? 1 n i2 ? 1 n i ? 1 ? n(n ?1)(2n ?1) ? 1 ? n(n ?1)

(3) i?1 j?1 k?1

i?1 j?1

i?1 2

2 i?1

2 i?1 2

6

22

? n(n ?1)(n? 2) 6

1.3 指出下列个算法的功能,并求其时间复杂度。

(1) int sum1(int n)

(2) int sum2 (int n)

{

{ int s=0;

int p=1,s=0;

for ( int i=1; i<=n; i++)

for (int i=1;i<=n; i++)

{ int p=1;

{ p*= i; s+=p;}

for (int j=1; j<=i; j++) p*=j;

return s;

s+=p;

}

}

return s;

}

解:
n
(1) ? i! , i?1
n
(2) ? i! , i?1

T(n)=O(n) T(n)=O(n2)

.

资料

1.4 算法设计 有 3 枚硬币,其中有 1 枚是假的,伪币与真币重量略有不同。如何借用一架 天平,找出伪币?以流程图表示算法。
上机练习题 要求:给出问题分析、算法描述、源程序及运行截图,在线提交。 1. 设 a, b, c 为 3 个整数,求其中位于中间值的整数。

开始

是 A=B?
否 是
A=C?

A是伪币

C是伪币 B是伪币

结束

.

资料

第 2 章 线性表

1. 设计算法:在顺序表中删除值为 e 的元素,删除成功,返回 1; int Sqlist<T>::DeleteElem( T e )

否则,返回 0。

{ for (i=1; i<=length; i++) // 按值顺序查找 * i 可从 0 开始

if (elem[i-1]= =e) // 找到,进行删除操作

{ for ( j=i; j<length; j++) // ai 至 an 依次前移

Elem[j-1] = elem[j];

length - - ;

// 表长减一

return 1 ;

//删除成功,返回 1

}

return 0 ; // 未找到,删除不成功,返回 0

}

2. 分析顺序表中元素定位算法 int SqList<T>::Locate ( T 解:设表长为 n,等概率下,每个元素被定位的概率为:p=1/n

e ) 的时间复杂度。

定位成功第 i 个元素,需比较 i 次

3.对于有头结点的单链表,分别写出定位成功时,实现下列定位 语句序列。

? ? f (n) ? n 1 ? i ? 1 n i ? 1 ? n(n ?1) ? n ?1

i?1 n

n i?1 n

2

2

(1) 定位到第 i 个结点 ai; (2) 定位到第 i 个结点的前驱 ai-1;

p=head; j=0; while ( p && j<i ) { p=p->next; j++;} p=head; j=0; while ( p && j<i-1 ) { p=p->next; j++;}

.

资料

(3) 定位到尾结点;

p=head; while ( p ->next ) p=p->next;

(4) 定位到尾结点的前驱。

p=head; while ( p->next->next ) p=p->next;

4.描述一下三个概念的区别:头指针,头结点,首元结点。并给 头指针:是一个指针变量,里面存储的是链表中首结点的地址,并以此来标识一个链表。

予图示。

头结点:附加在第一个元素结点之前的一个结点,头指针指向头结点。

首元结点:指链表中的第一个元素结点。

头指针 头结点

首(元)结点

a1

a2

尾(元)结点
… ... an ^

.

资料

5. 对于无头结点单链表,给出删除第 i 个结点的算法描述。 template <calss T> T LinkList<T>::Delete(int i)
6. 用教材定义的顺序表的基本操作实现下列操作: template <calss T> int DeleteElem(SqList L, T e)

template <calss T> T LinkList<T>::Delete(int i) { // 在单链表上删除第 i 个数据元素 if ( head==NULL) throw “表空!”; // 空表,不能删 else if ( i==1) { // 删除第 1 个元素 p=Head; x=p->data; // 保存被删元素值 Head= p->next ; delete p ; } else { // 元素定位到第 ai-1 p=Head; j=1 ; // 定位查找起始位置 while { p->next && j<i-1 } { p=p->next; j++ ; } if ( !p->next || j>i-1 ); // 定位失败 throw “删除位置不合理”; else { // 定位成功,进行结点删除 q=p->next; x=p>data; p->next=q->next; delete q; } retrun x; // 返回被删除元素值 }//#
#include “SqList.h“ template <calss T> int DeleteElem(SqList L, T e){ //
i = L.LocateElem(e) ; // 按值查找

.

资料

7. 已知 L 是有表头结点的单链表,且 P 结点既不是首元结点, 也不是尾结点,试写出实现下列功能的语句序列。
(1) 在 P 结点后插入 S 结点; (2) 在 P 结点前插入 S 结点; (3) 在表首插入 S 结点; (4) 在表尾插入 S 结点.

if (!i) // 未找到 return 0;
else // 找到 delete (i) ; // 删除被找到的元素 } 【解】 (1) s->next=p->next; p->next=s; (2) q=L; while( q->next!=p) q=q->next; s->next=p 或 q->next ; q ->next=s; (3) s->next=L->next; L->next=s; (3) q=L; while( q->next!=NULL) q=q->next; s->next= q->next ; q->next=s;

上机练习题 要求:给出问题分析、算法描述、源程序及运行截图,在线提交。 编程实现:删除单链表中值为 e 的元素。

.

第 3 章 栈与队列
1. 铁路进行列车调度时, 常把站台设计 成栈式结构的站台,如右图所示。试问: 若进站的六辆列车顺序如上所述, 那么 是否能够得到 325641 和 154623 的出站序 列, 如果不能, 说明为什么不能; 如果 能, 说明如何得到(即写出"进栈"或"出 栈"的序列)。

资料

123456

解:325641 可以 154623 不可以。

.

资料

2. 简述以下算法的功能(栈的元素类型为 int )。 (1) status algo_1( SqStack S ) { int i, n, A [255]; n=0; while (!S.StackEmpty() ) { n++; A[n]= S.Pop(); } for ( i=1; i<= n ; i++) S.Push(A[i]); } (2) status algo_2(SqStack S, int e) { SqStack T; int d; while (!S.tackEmpty()) { d = S.Pop(); if (d!=e ) T.Push(d); } while (!T.StackEmpty()) { d=T.Pop(); T.Push(d); } }

解:(1) 借助一个数组,将栈中的元素逆置。 (2) 借助栈 T,将栈 S 中所有值为 e 的数据元素删除之。

3.编写一个算法,将一个非负的十进制整数 N 转换为 B 进制数, #include “stack.h”

并输出转换后的结果。当 N=248D,B 分别为 8 和 16 时,转换后 int NumTrans( int N, int B) {//十进制整数 N 转换为 B 进制数

的结果为多少?

stack<int> S; // 建立一个栈

while( N!=0) { // N 非零

i=N%B ; // 从低到高,依次求得各位

.

资料

N=N/B;

S.push(i); }// 各位入栈

while ( !S.StackEmpty()) { // 栈不空

{ i= S.pop();

If (i>9) i=’A’+10-i;

cout<< S.pop(); }// 依次出栈,得到从高到低的输出结果

}

}//#

4 借且栈,设计算法:假设一个算术表达式中包含“(”、“)”括号, 解:以字符串存储表达式,也可以边输入边判断。

对一个合法的数学表达式来说,括号“(”和“)”应是相互匹配的。

顺序扫描表达式,左括号,入栈;右括号,如果此时栈空,表示多右括号,不匹

若匹配,返回 1;否则,返回 0。

配;如果栈不空,出栈一个左括号。扫描结束,如果栈空,表示括号匹配;否则,括

号不匹配,多左括号。

int blank_match(char *exp) { 用字符串存表达式

SqStack<char> s; // 创建一个栈

char *p=exp; // 工作指针 p 指向表达式首

while ( *p!=’=’) { // 不是表达式结束符

switch(p) {

case ’(’: //左括号,入栈

s.push(ch); break;

case ’)’ // 右括号

if (s.StackEmpty()) return 0; // 栈空,不匹配,多右括号

else { s.Pop(); break; } // 左括号出栈

}//switch

p++; // 取表达式下一个字符

} // while

if (!s.StackEmpty()) // 表达式结束,栈不空

.

5. 简述栈和队列的逻辑特点,各举一个应用实例。 6. 写出下列中缀表达式的后缀表达式。 (1)-A+B-C+D (2)(A+B)*D+E/(F+A*D)+C (3) A&&B||!(E>F)
7.计算后缀表达式:4 5 * 3 2 + - 的值。
8.将下列递推过程改写为递归过程。 void recursion( int n ) {
int i=n; while( i>1) {
cout<<i; i--; } }

资料
return 0 ; //不匹配,多左括号 else
return 1 ; // 匹配 } //#
(1) A-B+C-D+ (2) AB+D*EFAD*+/+C+ (3) AB&&EF ! ||
解:15 解:void recurision(int j)
{ if (j>1) { cour<<j; recurision(j-1); }
}

.

9.. 将下列递归过程改写为非递归过程。 void test( int &sum) {
int x; cin>>x; if (x==0) sum=0; else { test(sum); sum+=x; } cout<<sum; }

资料
解:void test (int &sum) { stack S; //借助一个栈
int x; cin>>x; while (x) {
S.push(x); cin>>x; } sum=0; cout<<sum; while ( x=S.pop() ) {
sum+=x; cout<<sum; } } //

10. 简述以下算法的功能(栈和队列的元素类型均为 int)。 解:利用栈,将队列中的元素逆置
.

资料

void algo (Queue &Q) {
Stack S; //创建一个栈 int d; while (!Q.QueueEmpty()) {
d=DeQueue(Q); S.Push(d); } while (!S.StackEmpty()) {
d=S.Pop();Q.EnQueue(d); } } 12. 假设以数组 se[m]存放循环队列的元素,同时设变量 rear 和 front 分别作为队首、队尾指针,且队首指针指向队首前一个 位置,队尾指针指向队尾元素处,初始时,rear==fornt==-1。 写出这样设计的循环队列入队、出队的算法。

解:采用教材队空与队满判别方法。为了区分队空与队满条件,牺牲一个元素空间。 即:rear==front, 为队空;rear==(front+1)%m,为队满。 template <calss T> void EnQueue( T Se[], T e, int m ) { //入队
if ( rear+1)%m =fornt ) { //队满,不能插入 throw “队满,不能插入!”
else { rear = (rear+1) % m ; // 队尾指针后移 se[rear]=e; // 元素入队 return ;
} }//#

template <calss T> T DnQueue( T Se[], int m ) { // 出队
if ( rear= =fornt ) //队空,不能出队! throw “队空,不能出队!”

.

资料
else { front = (front+1)%m ; // 指针后移,指向队首元素 e =se[front]; // 取队首元素 return e ; }
}//#
上机练习题 要求:给出问题分析、算法描述、源程序及运行截图,在线提交。 1.借助栈,实现单链表上的逆置运算。
.

资料

第4章 串 1. 试问执行以下函数会产生怎样的输出结果?
void demonstrate( ) {
StrAssign( s, 'THIS IS A BOOK'); StrRep ( s, StrSub(s, 3, 7), 'ESE ARE'); StrAssign( t, StrConcat ( s, 'S' ) ) ; StrAssign(u, 'XYXYXYXYXYXY' ); StrAssign(v, StrSub ( u, 6, 3 ) ); StrAssign(w, 'W'); cout<<“'t=”<< t<<endl; cout<<“v=”<< v; cout<<“u=”<< StrRep(u, v, w); } // demonstrate 2.设字符串 S=‘aabaabaabaac',P=‘aabaac' 1)给出 S 和 P 的 next 值和 nextval 值; 2)若 S 作主串,P 作模式串,试给出 KMP 算法的匹配过程。
3. 算法设计 串结构定义如下:
struct SString

解:t= THESE ARE BOOKS v= YXY w= XWXWXW
1)S 的 next 与 nextval 值分别为 012123456789 和 002002002009, p 的 next 与 nextval 值分别为 012123 和 002003
2)利用 KMP 算法的匹配过程: 第一趟匹配:aabaabaabaac aabaac(i=6,j=6) 第二趟匹配:aabaabaabaac (aa)baac 第三趟匹配:aabaabaabaac (成功) (aa)baac

.

资料

{

char *data; // 串首址

int len;

// 串长

int StrSize; // 存放数组的最大长度.

};

(1) 编写一个函数,计算一个子串在一个字符串中出现的次数, 解:int str_count (SString S, SString T) {

如果不出现,则为 0。

int i, j,k, count=0;

int str_count (SString S, SString T )

for ( i=0; S.data[i]; i++) {

for ( j=i, k=0; (S.data[j]==T.data[k]; j++,k++)

if ( k= =T.len-1)

count + +;

}

return count;

}

(2) 编写算法,从串 s 中删除所有和串 t 相同的子串。

解:

int SubString_Delete(SString &s, SString t )

//从串 s 中删除所有与 t 相同的子串,并返回删除次数

{

for ( n=0, i=0; i<=s.len-t.len; i++ )

{

for ( j=0; j<t.len && s[i+j]==t[i]; j++);

if (j > t.len) //找到了与 t 匹配的子串

{

for ( k = i; k<s.len-t.len; k++ )

s[k]=s[k+t.len]; //左移删除

.

资料

(2) 编写一个函数,求串 s 和串 t 的一个最长公共子串。 void maxcomstr( SString *s, SString *t)

s.len-=t.len ;

n++; // 被删除次数增 1 }

}//for

return n;

}//Delete_SubString

解:void maxcomstr( SString *s, SString *t) {

int index=0,len1=0, i,j,k,len2;

i=0;

// 作为扫描 s 的指针

while ( i <s.len) {

j = 0; // 作为扫描 t 的指针

while ( j < t.len ) {

if (s.data[i] = = t.data[j] ) {// 序号为 i,长度为 len2 的子



len2 =1; // 开始计数

for ( k=1; s.data[i+k]==t.data[j+k] &&

s.data[i+k]!=NULL; k++ )

len2++;

if ( len2>len1) { // 将较大长度者给 index 和 len1

index=i;

len1=len2;

}

j + = len2;

} //if

else j++;

}//while

cout<<”最长公共子串:”

.

资料

1. 已知下列字符串 a = 'THIS', f = 'A SAMPLE', c = 'GOOD', d ='NE', b =
' ', s = StrConcat(a,StrConcat(StrSub(f,2,7),StrConcat(b,
StrSub (a,3,2)))), t = StrRep(f, StrSub (f,3,6),c), u = StrConcat(StrSub(c,3,1),d), g = 'IS', v=
StrConcat(s,StrConcat(b,StrConcat(t,StrConcat(b,u)))), 试 问 : s, t, v, StrLength(s), StrIndex(v,g),
StrIndex(u,g) 各是什么 ? 已知:s='(XYZ)+* ',t='(X+Z)*Y'。试利用下列运算,将 s 转 化为 t。
联接:StrConcat ( &S,T ) 求子串:(char *) StrSub( S, i, len ) 置换:StrRep ( &S, T, R ) 上机练习题 要求:给出问题分析、算法描述、源程序及运行截图,在线提交。 串结构定义如下: struct SString {
char *data; // 串首址 int len; // 串长

for ( i=0; i<len1; i++; ) cout<<s.data[index+1];
}// #

.

资料
int StrSize; // 存放数组的最大长度. }; 求:串 S 所含不同字符的总数和每种字符的个数,不区分英文字 母的大小写。
.

资料

第 5 章 数组与压缩矩阵
1. 假设有二维数组 A6×8,每个元素用相邻的 6 个字节存储,存储器按 字节编址。已知 A 的起始存储位置(基地址)为 1000,计算:
(1) 数组 A 的体积(即存储量); (2) 数组 A 的最后一个元素 a57 的第一个字节的地址; (3) 按行存储时,元素 a14 的第一个字节的地址; (4) 按列存储时,元素 a47 的第一个字节的地址。

解:(1)6×8×6 = 288Byte (2)1000+288-6=1282; (3)1000+(1×8+4)×6=1072 (4)1000+(7×6+4)×6=1276

2. 假设按低下标优先存储整数数组 A9×3×5×8 时,第一个元素的字节地址是 100,每个整数占四个字节。问下列元素的存储地址是什么?

(1) a0000

(2) a8247

3.一个稀疏矩阵如图所示

0 30 0 00

(1) 给出三元组存储示意图;

0 2 05 0 0 A=

(2) 给出带行指针向量的链式存储示意图; 0 0 0 0 0 0

9 0 0 0 0 1 4×6

(3) 十字链表存储示意图。

解:(1) 100 (2) 100+8×3×5×8+2×5×8+4×8+7=4500

M.data[ ] i j e

00 1 3

11 1 2

21 3 5

33 0 9

43 5 1

M.mu 4

M.nu 6

(1)

M.tu 5

(2)

A
01 3∧ 11 2 ∧
309

23 5 ∧ 4 5 1∧

A.chead

(3)

A.rhead
A.mu 4 A.nu 6 A.tu 5
^

^
0 13 ^
1 12 ^
3 09 ^

1 35 ^^
3 51
^^

.

资料

4. 算法设计:一个按行优先存储的 n*n 矩阵,就地转置。

解:void trans ( ElemType A[], int n) {

int i, j;

ElemType tmp;

for ( i = 0; i<n;i++)

for ( j=0;j<i;j++) {

A[i*n+j]??A[j*n+i];

}

}

5. 算法设计:设定整数数组 B[m][n]的数据在行列方向上都按从小到大 解:void find( int B[][], int x, int m, int n ) {

的顺序排列,且整型变量 x 中的数据在 B 中存在。试设计一个算法,找

int i = 0, j = n-1 ;

出一对满足 B[i][j]= = x 的 i,j 值。要求比较次数不超过 m+n。

while (B[i][j] != x ) {

if ( B[i][j] > x ) j - - ;

else i + +;

}

out<<”i=”<<i<<”,j=”<<j<<endl;

}//#

上机练习题 要求:给出问题分析、算法描述、源程序及运行截图,在线提交。

选用数组作为数据结构,编程求解 Josephus 问题。手工推演下列测试用

例,并检查程序的正确性。

人数 n

开始报数的人 s 密码 m

9

1

5

9

1

0

殷习 P30 2-2 n=,s=1,m=5 时, 出局顺序为:5,1,7,4,3,6,9, 2,8 m=0, 报错,m=0 是无效参数; m=10,时间代价最大

.

9

1

10

资料
出局顺序为:1,3,6,2,9,5,7,4,8 源程序 Void Josephus(in A[], int n,s,m) {
int i, j, k, tmp; if (m==0) {
cerr<<”m=0 是无效的参数!”<<endl; return; } for(i=0;i<n;i++) A[i]=i+1; // 初始化 i=s-1; // 报名超始位置 for(k=n;k>=1;k--) { // 逐个出局,执行 n-1 次;
if (i==k) i=0; // 第 n 个人,下标为 0 i = (i+m-1)%k; // 寻找出局位置 if ( i ! = k-1 ) { // 把出局者移到最后
tmp=A[i]; // 保留出局序号 for ( j = i; j < k-1; j++ ) A[j] =A[j+1] ; // 第 i 至第 k 个元素依次前移 A[k-1]=tmp; } // 出局者移至 k-1 处 } for(k=0;k<n/2;k++) //全部逆置,得到出局序列。 A[k]=A[n-k-1]; A[n-k-1]=tmp; } }

.


网站首页 | 网站地图
All rights reserved Powered by 酷我资料网 koorio.com
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。3088529994@qq.com