大数据结构习题(有问题详解)

第1章 绪

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

并指出它们分别属于何种结构。 (2) 线性表

(1) A= ( D，R )，其中，D = { a

1

，a

2

，a

3

，a

4

}， R={ } (3) 树 (4) 图

(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，

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

(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>}

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

(2)



1n

i1j1k1

nnn

3

(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;

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

(1) int sum1(int n)

{

int p=1,s=0;

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

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

return s;

}

i(i1)1

n

2

1

n

1n(n1)(2n1)1n(n1)

1jii ••



2



22

i1

2622

(3)

i1j1k1i1j1i1i1



n(n1)(n2)

6

ni

j

nin

(2) int sum2 (int n) 解：

{ int s=0;

n

(1)

i!

, T(n)=O(n)

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

i1

{ int p=1;

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

n

2

(2)

i!

, T(n)=O(n)

s+=p;

i1

}

return s;

}





1.4 算法设计

有3枚硬币，其中有1枚是假的，伪币与真币重量略有不同。如何借用一架

天平，找出伪币？以流程图表示算法。

开始

是

A=B？

C是伪币

否

是

A=C？B是伪币

否

A是伪币

结束

上机练习题

要求：给出问题分析、算法描述、源程序及运行截图，在线提交。

1. 设 a, b, c为3个整数，求其中位于中间值的整数。

第2章 线性表

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

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

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

{ for ( j=i; j

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

length - - ; // 表长减一

return 1 ; //删除成功，返回 1

}

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

}

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

e ) 的时间复杂度。 定位成功第i个元素，需比较i次

n

11

n

1n(n1)n1

f(n)•ii•



n

i1

n



i1

n22

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

语句序列。

(1) 定位到第i个结点a

i

；

(2) 定位到第i个结点的前驱a

i-1

；

p=head; j=0;

while ( p && jnext; j++;}

p=head; j=0;

while ( p && jnext; j++;}

(3) 定位到尾结点； p=head;

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

p=head;

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

头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。

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

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

头指针

头结点

首(元)结点

尾(元)结点

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

4.描述一下三个概念的区别：头指针，头结点，首元结点。并给

予图示。

a

1

a

2

…... a

n

^

5. 对于无头结点单链表，给出删除第i个结点的算法描述。

template

T LinkList::Delete(int i)

template

T LinkList::Delete(int i) { // 在单链表上删除第i个数据元素

if ( head==NULL) throw “表空!”; // 空表，不能删

else if ( i==1) { // 删除第1个元素

p=Head; x=p->data; // 保存被删元素值

Head= p->next ;

delete p ;

}

else { // 元素定位到第a

i-1

p=Head; j=1 ; // 定位查找起始位置

while { p->next && j

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

int DeleteElem(SqList L, T e){ //

i = Elem(e) ; // 按值查找

6. 用教材定义的顺序表的基本操作实现下列操作：

template

int DeleteElem(SqList L, T e)

if (!i) // 未找到

return 0;

else // 找到

delete (i) ; // 删除被找到的元素

}

7. 已知L是有表头结点的单链表，且P结点既不是首元结点，

也不是尾结点，试写出实现下列功能的语句序列。

(1) 在P结点后插入S结点；

(2) 在P结点前插入S结点；

(3) 在表首插入S结点；

(4) 在表尾插入S结点.

【解】

(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不可以。

够得到325641和154623的出站序列, 如果不能, 说明为什么不

能; 如果能, 说明如何得到(即写出"进栈"或"出栈"的序列)。

2. 简述以下算法的功能（栈的元素类型为 int ）。

(1) status algo_1( SqStack S ) {

int i, n, A [255];

n=0;

while (!mpty() ) { n++; A[n]= (); }

for ( i=1; i<= n ; i++) (A[i]);

}

(2) status algo_2(SqStack S, int e) {

SqStack T;

int d;

while (!pty()) {

d = ();

if (d!=e ) (d); }

while (!mpty()) {

d=();

(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 S; // 建立一个栈

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

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

N=N/B;

(i); }// 各位入栈

while ( !mpty()) { // 栈不空

{ i= ();

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

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

}

}//#

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

号，对一个合法的数学表达式来说，括号“(”和“)”应是相互 顺序扫描表达式，左括号，入栈；右括号，如果此时栈空，表示多右括号，不匹

匹配的。若匹配，返回1；否则，返回0。 配；如果栈不空，出栈一个左括号。扫描结束，如果栈空，表示括号匹配；否则，括

号不匹配，多左括号。

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

SqStack s; // 创建一个栈

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

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

switch(p) {

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

(ch); break;

case ’)’ // 右括号

if (mpty()) return 0; // 栈空，不匹配，多右括号

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

}//switch

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

} // while

if (!mpty()) // 表达式结束，栈不空

return 0 ; //不匹配，多左括号

else

return 1 ; // 匹配

} //#

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<

}

(1) A-B+C-D+

(2) AB+D*EFAD*+/+C+

(3) AB&&EF ! ||

解：15

解：void recurision(int j)

{ if (j>1)

{ cour<

recurision(j-1); }

}

9.. 将下列递归过程改写为非递归过程。

void test( int &sum) {

int x;

cin>>x;

if (x==0) sum=0;

else {

test(sum); sum+=x; }

cout<

}

解：void test (int &sum)

{ stack S; //借助一个栈

int x;

cin>>x;

while (x) {

(x);

cin>>x; }

sum=0;

cout<

while ( x=() ) {

sum+=x; cout<

} //

10. 简述以下算法的功能（栈和队列的元素类型均为 int）。 解：利用栈，将队列中的元素逆置

void algo (Queue &Q)

{

Stack S; //创建一个栈

int d;

while (!mpty()) {

d=DeQueue(Q); (d); }

while (!mpty()) {

d=();e(d); }

}

12. 假设以数组se[m]存放循环队列的元素，同时设变量rear

和front分别作为队首、队尾指针，且队首指针指向队首前一个

位置，队尾指针指向队尾元素处，初始时，rear==fornt==-1。

写出这样设计的循环队列入队、出队的算法。

解：采用教材队空与队满判别方法。为了区分队空与队满条件，牺牲一个元素空间。

即：rear==front， 为队空；rear==(front+1)%m，为队满。

template

void EnQueue( T Se[], T e, int m ) { //入队

if ( rear+1)%m =fornt ) { //队满，不能插入

throw “队满，不能插入!”

else {

rear = (rear+1) % m ; // 队尾指针后移

se[rear]=e; // 元素入队

return ;

}

}//#

template

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<

cout<<“v=”<< v;

cout<<“u=”<< StrRep(u, v, w);

} // demonstrate

2.设字符串S=‘aabaabaabaac'，P=‘aabaac'

1）给出S和P的next值和nextval值；

2）若S作主串，P作模式串，试给出KMP算法的匹配过程。

解：t= THESE ARE BOOKS

v= YXY

w= XWXWXW

1）S的next与nextval值分别为9和9，

p的next与nextval值分别为012123和002003

2）利用KMP算法的匹配过程：

第一趟匹配：aabaabaabaac

aabaac(i=6,j=6)

第二趟匹配：aabaabaabaac

(aa)baac

第三趟匹配：aabaabaabaac

(成功) (aa)baac

3. 算法设计

串结构定义如下：

struct SString

{

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; [i]; i++) {

for ( j=i, k=0; ([j]==[k]; j++,k++)

if ( k= =-1)

count + +;

}

return count;

}

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

int SubString_Delete(SString &s, SString t )

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

{

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

{

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

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

{

for ( k = i; k<; k++ )

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

-= ;

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

}//for

return n;

}//Delete_SubString

(2) 编写一个函数，求串s和串t 的一个最长公共子串。

void maxcomstr( SString *s, SString *t)

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

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

i=0; // 作为扫描s的指针

while ( i <) {

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

while ( j < ) {

if ([i] = = [j] ) {// 序号为i，长度为len2的子

串

len2 =1; // 开始计数

for ( k=1; [i+k]==[j+k] &&

[i+k]!=NULL; k++ )

len2++;

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

index=i;

len1=len2;

}

j + = len2;

} //if

else j++;

}//while

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

for ( i=0; i

cout<<[index+1];

}// #

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; // 串长

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

};

求：串S所含不同字符的总数和每种字符的个数，不区分英文字

母的大小写。

第5章 数组与压缩矩阵

1. 假设有二维数组 A

6×8

，每个元素用相邻的 6 个字节存储，存储器按

字节编址。已知 A 的起始存储位置(基地址)为 1000，计算：

(1) 数组 A 的体积（即存储量）;

(2) 数组 A 的最后一个元素 a

57

的第一个字节的地址;

(3) 按行存储时，元素 a

14

的第一个字节的地址;

(4) 按列存储时，元素 a

47

的第一个字节的地址。

2. 假设按低下标优先存储整数数组A

9×3×5×8

时，第一个元素的字节地址

是 100，每个整数占四个字节。问下列元素的存储地址是什么？

(1) a

0000

(2) a

8247

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

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

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

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

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

解：(1）6×8×6 = 288Byte

(2）1000+288-6=1282；

(3）1000+(1×8+4)×6=1072

(4）1000+(7×6+4)×6=1276

解：(1) 100

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

(1) (2)

(3)

A

0

1

3

∧

1

1

2

∧

3

0

9

4

5

1

∧

2

3

5

∧

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

int i, j;

ElemType tmp;

for ( i = 0; i

for ( j=0;j

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

}

}

5. 算法设计：设定整数数组B[m][n]的数据在行列方向上都按从小到大

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

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

解：void find( int B[][], int x, int m, int n ) {

int i = 0, j = n-1 ;

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

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

else i + +;

}

out<<”i=”<

}//#

殷习 P30 2-2

n=,s=1,m=5时，

出局顺序为：5,1，7,4，3,6，9, 2，8

m=0， 报错，m=0是无效参数；

m=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是无效的参数！”<

return; }

for(i=0;i

i=s-1; // 报名超始位置

上机练习题

要求：给出问题分析、算法描述、源程序及运行截图，在线提交。

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

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

人数n

9

9

9

开始报数的人s

1

1

1

密码m

5

0

10

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

A[k]=A[n-k-1];

A[n-k-1]=tmp; }

}